Chapter 9 Support Vector Machines

This notebook is a rough outline of solutions to the applied exercises in Chapter 9 of An Introduction to Statistical Learning (James et al. (2013)1).

Setup

library(ISLR)
library(e1071)
library(cowplot)
library(latex2exp)
library(tidyverse)
library(patchwork)
theme_set(theme_bw())

# Given a filename, return the filepath. Default folder is the `data` folder in the current working directory.
get_path <- function(filename) {
  str_c(getwd(), "data", filename, sep = "/")
}

# Load my functions:
source("/home/brian/R/dir/Util/bh_functions.R")

# Colors:
ISLR_blue <- "#176FC0"
ISLR_brown <- "#94340E"
ISLR_lightblue <- "#68A5DB"
ISLR_orange <- "#CC5318"

# Functions for plotting `svm` objects:
dist2point <- function(coef, p) {
  dist <- (coef[2]*p[1] + coef[3]*p[2] +coef[1]) / sqrt(coef[2]^2 + coef[3]^2)
  unname(dist)
}

svc_margins <- function(svc) {
  slope <- -coef(svc)[3]/coef(svc)[2] # slope
  int0 <- -coef(svc)[1] # hyperplane intercept
  v1 <- svc$SV[apply(svc$SV, 1, function(v) dist2point(coef(svc), v)) %>% which.max(), ] # support vector 1
  v2 <- svc$SV[apply(svc$SV, 1, function(v) dist2point(coef(svc), v)) %>% which.min(), ] # support vector 2

  int1 <- v1[1] - slope*v1[2] # intercept of margin 1
  int2 <- v2[1] - slope*v2[2] # intercept of margin 2

  c(slope, int0, int1, int2) %>% unname()
}

svm_plot <- function(svm, df) {
  dat <- df
  x1 <- dat[ , 1]
  x2 <- dat[ , 2]
  y <- dat[ , ncol(dat)]
  
  grid <- expand.grid(seq(min(x1), max(x1), length.out = 100),
                      seq(min(x2), max(x2), length.out = 100)) 
  names(grid) <- names(dat)[1:2]
  preds <- predict(svm, grid)
  dat_ <- data.frame(grid, preds)
  
  cols <- c('1' = '#f53224', '-1' = '#1a6eff') # 1 := red, -1 := blue; three shades darker on https://www.w3schools.com/colors/colors_picker.asp
  tiles <- c('1' = '#F8766D', '-1' = '#619CFF')
  shapes <- c('support' = 4, 'notsupport' = 1)
  dat$support <- 'notsupport'
  dat[svm$index, 'support'] <- 'support'

  g <- ggplot(dat_, aes(x = x2, y = x1)) +
          geom_tile(aes(fill = preds), color = "white", alpha = 0.3) + 
          scale_fill_manual(name = "Pred. Class", values = tiles)
  
  if(svm$kernel == 0) { # if linear kernel add margins
    margins <- svc_margins(svm)
    g <- g + 
          #geom_abline(aes(slope = margins[1], intercept = margins[2]), col = "green") + # line of separation
          geom_abline(aes(slope = margins[1], intercept = margins[4]), col = cols[1]) + #  1 := red
          geom_abline(aes(slope = margins[1], intercept = margins[3]), col = cols[2]) # -1 := blue
  }

  g <- g +
        geom_point(data = dat, aes(color = y, shape = support), size = 2, show.legend = FALSE) +
        scale_color_manual(values = cols) +
        scale_shape_manual(values = shapes) +
        scale_x_continuous(expand = c(0, 0)) +
        scale_y_continuous(expand = c(0, 0)) +
        guides(fill = guide_legend(override.aes = list(alpha = 1))) +
        theme_bw() +
        ggtitle('SVM Classification Plot') +
        theme(plot.title = element_text(hjust = 0.5))
  g
}

# Return vector of the names of numeric columns in a data frame:
numeric_cols <- function(df) {
  is_numeric_cols <- map_lgl(df, is.numeric)
  return(names(df)[is_numeric_cols])
}

Exercise 4

Generate a simulated two-class data set with 100 observations and two features in which there is a visible but non-linear separation between the two classes. Show that in this setting, a support vector machine with a polynomial kernel (with degree greater than 1) or a radial kernel will outperform a support vector classifier on the training data. Which technique performs best on the test data? Make plots and report training and test error rates in order to back up your assertions.

Generate data:

# Prelims:
set.seed(1)

# Data:
x1 <- rnorm(100)
x2 <- 4 * x1^2 + 1 + rnorm(100)

class <- sample(100, 50)
x2[class] <- x2[class] + 3
x2[-class] <- x2[-class] - 3

y <- rep(-1, 100)
y[class] <- 1

dat <- data.frame(x1 = x1,
                  x2 = x2,
                  y = as.factor(y))

# Errors:
error_train <- c()
error_test <- c()

# Train/Test
train <- sample(100, 80)
test = -train

# Plots:
ggplot(dat) +
  geom_point(aes(x1, x2, group = y, color = y)) +
  theme_bw()

Support Vector Classifier

Train a support vector classifier (linear kernel) on a range of values for cost:

set.seed(1)
tune.out_4_svc <- tune(svm, y ~ ., data = dat[train, ], kernel = "linear", ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100)))
summary(tune.out_4_svc)

Parameter tuning of ‘svm’:

- sampling method: 10-fold cross validation 

- best parameters:

- best performance: 0.1125 

- Detailed performance results:
NA

Extract the best model and print summary:

bestmod_4_svc <- tune.out_4_svc$best.model
summary(bestmod_4_svc)

Call:
best.tune(method = svm, train.x = y ~ ., data = dat[train, ], ranges = list(cost = c(0.001, 0.01, 0.1, 1, 
    5, 10, 100)), kernel = "linear")


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  linear 
       cost:  0.1 

Number of Support Vectors:  56

 ( 28 28 )


Number of Classes:  2 

Levels: 
 -1 1

Plot the decision boundary:

#plot(bestmod_4_svc, dat[train, ])
svm_plot(bestmod_4_svc, dat[train, ])

The linear classifier fails to accurately capture the non-linearity of the decision boundary.

Training error

mean(dat[train, "y"] != predict(bestmod_4_svc, newdata = dat[train, ]))
[1] 0.1125
svc_error_train <- mean(summary(bestmod_4_svc)$fitted != y[train])
error_train <- c(error_train, "svc" = svc_error_train)
svc_error_train
[1] 0.1125

Test Error

ypred <- predict(bestmod_4_svc, dat[test, ])
table(predict = ypred, truth = y[test])
       truth
predict -1 1
     -1  8 0
     1   3 9
svc_error_test <- mean(ypred != y[test])
error_test <- c(error_test, "svc" = svc_error_test)
svc_error_test
[1] 0.15

Support Vector Machine - Polynomial Kernel (\(d\) = 2)

Train a support vector machine (polynomial kernel, \(d\) = 2) on a range of values for cost:

set.seed(1)
tune.out_4_svm <- tune(svm, y ~ ., data = dat[train, ], kernel = "polynomial", degree = 2, ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100)))
summary(tune.out_4_svm)

Parameter tuning of ‘svm’:

- sampling method: 10-fold cross validation 

- best parameters:

- best performance: 0.2875 

- Detailed performance results:
NA

Extract the best model and print summary:

bestmod_4_svm <- tune.out_4_svm$best.model
summary(bestmod_4_svm)

Call:
best.tune(method = svm, train.x = y ~ ., data = dat[train, ], ranges = list(cost = c(0.001, 0.01, 0.1, 1, 
    5, 10, 100)), kernel = "polynomial", degree = 2)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  polynomial 
       cost:  5 
     degree:  2 
     coef.0:  0 

Number of Support Vectors:  63

 ( 32 31 )


Number of Classes:  2 

Levels: 
 -1 1

Plot the decision boundary:

#plot(bestmod_4_svm, dat[train, ])
svm_plot(bestmod_4_svm, dat[train, ])

The degree-2 polynomial kernel captures some of the non-linearity of the decision boundary, but there are many errors.

Training error

#mean(dat[train, "y"] != predict(bestmod_4_svm, newdata = dat[train, ]))
svm_error_train <- mean(summary(bestmod_4_svm)$fitted != y[train])
error_train <- c(error_train, "svm (d = 2)" = svm_error_train)
svm_error_train
[1] 0.275

Test Error

ypred <- predict(bestmod_4_svm, dat[test, ])
table(predict = ypred, truth = dat[test, "y"])
       truth
predict -1 1
     -1  6 2
     1   5 7
svm_error_test <- mean(ypred != y[test])
error_test <- c(error_test, "svm (d = 2)" = svm_error_test)
svm_error_test
[1] 0.35

Support Vector Machine - Polynomial Kernel (\(d\) = 3)

Train a support vector machine (polynomial kernel, \(d\) = 3) on a range of values for cost:

set.seed(1)
tune.out_4_svm_2 <- tune(svm, y ~ ., data = dat[train, ], kernel = "polynomial", degree = 3, ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100)))
summary(tune.out_4_svm_2)

Parameter tuning of ‘svm’:

- sampling method: 10-fold cross validation 

- best parameters:

- best performance: 0.3875 

- Detailed performance results:
NA

Extract the best model and print summary:

bestmod_4_svm_2 <- tune.out_4_svm_2$best.model
summary(bestmod_4_svm_2)

Call:
best.tune(method = svm, train.x = y ~ ., data = dat[train, ], ranges = list(cost = c(0.001, 0.01, 0.1, 1, 
    5, 10, 100)), kernel = "polynomial", degree = 3)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  polynomial 
       cost:  1 
     degree:  3 
     coef.0:  0 

Number of Support Vectors:  75

 ( 38 37 )


Number of Classes:  2 

Levels: 
 -1 1

Plot the decision boundary:

#plot(bestmod_4_svm_2, dat[train, ])
svm_plot(bestmod_4_svm_2, dat[train, ])

The degree-3 polynomial kernel captures some of the non-linearity of the decision boundary, but there many errors. It seems that a polynomial of degree 3 is worse than that of degree 2.

Training error

mean(dat[train, "y"] != predict(bestmod_4_svm_2, newdata = dat[train, ]))
[1] 0.4125
svm_2_error_train <- mean(summary(bestmod_4_svm_2)$fitted != y[train])
error_train <- c(error_train, "svm (d = 3)" = svm_2_error_train)
svm_2_error_train
[1] 0.4125

Test Error

ypred <- predict(bestmod_4_svm_2, dat[test, ])
table(predict = ypred, truth = dat[test, "y"])
       truth
predict -1  1
     -1  1  1
     1  10  8
svm_2_error_test <- mean(ypred != y[test])
error_test <- c(error_test, "svm (d = 3)" = svm_2_error_test)
svm_2_error_test
[1] 0.55

Support Vector Machine - Radial Kernel

Train a support vector machine with a radial kernel on a range of values for cost and gamma:

set.seed(1)
tune.out_4_svm_rad <- tune(svm, y ~ ., data = dat[train, ], kernel = "radial", ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100), gamma = c(0.5, 1, 2, 3, 4)))
summary(tune.out_4_svm_rad)

Parameter tuning of ‘svm’:

- sampling method: 10-fold cross validation 

- best parameters:

- best performance: 0.025 

- Detailed performance results:
NA

Extract the best model and print summary:

bestmod_4_svm_rad <- tune.out_4_svm_rad$best.model
summary(bestmod_4_svm_rad)

Call:
best.tune(method = svm, train.x = y ~ ., data = dat[train, ], ranges = list(cost = c(0.001, 0.01, 0.1, 1, 
    5, 10, 100), gamma = c(0.5, 1, 2, 3, 4)), kernel = "radial")


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  radial 
       cost:  5 

Number of Support Vectors:  17

 ( 8 9 )


Number of Classes:  2 

Levels: 
 -1 1

Plot the decision boundary:

#plot(bestmod_4_svm_rad, dat[train, ])
svm_plot(bestmod_4_svm_rad, dat[train, ])

The radial kernel has very accurately captured the decision boundary. In fact there are no errors.

Training error

#mean(dat[train, "y"] != predict(bestmod_4_svm_rad, newdata = dat[train, ]))
svm_rad_error_train <- mean(summary(bestmod_4_svm_rad)$fitted != y[train])
error_train <- c(error_train, "svm (radial)" = svm_rad_error_train)
svm_rad_error_train
[1] 0

Test Error

ypred <- predict(bestmod_4_svm_rad, dat[test, ])
table(predict = ypred, truth = dat[test, "y"])
       truth
predict -1  1
     -1 11  1
     1   0  8
svm_rad_error_test <- mean(ypred != y[test])
error_test <- c(error_test, "svm (radial)" = svm_rad_error_test)
svm_rad_error_test
[1] 0.05

Summary of Errors

sort(error_train)
svm (radial)          svc  svm (d = 2)  svm (d = 3) 
      0.0000       0.1125       0.2750       0.4125 
sort(error_test)
svm (radial)          svc  svm (d = 2)  svm (d = 3) 
        0.05         0.15         0.35         0.55 

The SVM with radial kernel has the best training and test errors. However, the linear support vector classifier outperformed both of the SVM’s with polynomial kernels.

Redo the analysis with a more complex non-linear decision boundary to see if the polynomial kernels outperform the linear kernel:

# Prelims:
set.seed(1)

# Data:
x1 <- rnorm(100)
x2 <- 4 * x1^2 + 1 + rnorm(100)

class <- sample(100, 50)
x2[class[1:25]] <- x2[class[1:25]] + 3
x2[class[25:50]] <- x2[class[25:50]] - 10
x2[-class] <- x2[-class] - 3

y <- rep(-1, 100)
y[class] <- 1

dat <- data.frame(x1 = x1,
                  x2 = x2,
                  y = as.factor(y))

# Errors:
error_train <- c()
error_test <- c()

# Train/Test
train <- sample(100, 80)
test = -train

# Plots:
ggplot(dat) +
  geom_point(aes(x1, x2, group = y, color = y)) +
  theme_bw()

Support Vector Classifier

set.seed(1)
tune.out_4_svc <- tune(svm, y ~ ., data = dat[train, ], kernel = "linear", ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100)))
bestmod_4_svc <- tune.out_4_svc$best.model
#plot(bestmod_4_svc, dat[train, ])
svm_plot(bestmod_4_svc, dat[train, ])

The linear classifier fails to capture any of the non-linear decision boundary.

Training error

svc_error_train <- mean(summary(bestmod_4_svc)$fitted != y[train])
error_train <- c(error_train, "svc" = svc_error_train)

Test Error

ypred <- predict(bestmod_4_svc, dat[test, ])
table(predict = ypred, truth = y[test])
       truth
predict -1  1
     -1  0  0
     1  11  9
svc_error_test <- mean(ypred != y[test])
error_test <- c(error_test, "svc" = svc_error_test)

Support Vector Machine - Polynomial Kernel (\(d\) = 2)

set.seed(1)
tune.out_4_svm <- tune(svm, y ~ ., data = dat[train, ], kernel = "polynomial", degree = 2, ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100)))
bestmod_4_svm <- tune.out_4_svm$best.model
#plot(bestmod_4_svm, dat[train, ])
svm_plot(bestmod_4_svm, dat[train, ])

The degree-2 polynomial kernel captures some of the non-linearity of the decision boundary, but there many errors.

Training error

#mean(dat[train, "y"] != predict(bestmod_4_svm, newdata = dat[train, ]))
svm_error_train <- mean(summary(bestmod_4_svm)$fitted != y[train])
error_train <- c(error_train, "svm (d = 2)" = svm_error_train)

Test Error

ypred <- predict(bestmod_4_svm, dat[test, ])
table(predict = ypred, truth = dat[test, "y"])
       truth
predict -1  1
     -1 10  4
     1   1  5
svm_error_test <- mean(ypred != y[test])
error_test <- c(error_test, "svm (d = 2)" = svm_error_test)

Support Vector Machine (Polynomial Kernel, \(d\) = 3)

set.seed(1)
tune.out_4_svm_2 <- tune(svm, y ~ ., data = dat[train, ], kernel = "polynomial", degree = 3, ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100)))
bestmod_4_svm_2 <- tune.out_4_svm_2$best.model
#plot(bestmod_4_svm_2, dat[train, ])
svm_plot(bestmod_4_svm_2, dat[train, ])

The degree-3 polynomial kernel captures some of the non-linearity of the decision boundary, but there many errors.

Training error

svm_2_error_train <- mean(summary(bestmod_4_svm_2)$fitted != y[train])
error_train <- c(error_train, "svm (d = 3)" = svm_2_error_train)

Test Error

ypred <- predict(bestmod_4_svm_2, dat[test, ])
svm_2_error_test <- mean(ypred != y[test])
error_test <- c(error_test, "svm (d = 3)" = svm_2_error_test)

Support Vector Machine - Radial Kernel

set.seed(1)
tune.out_4_svm_rad <- tune(svm, y ~ ., data = dat[train, ], kernel = "radial", ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100), gamma = c(0.5, 1, 2, 3, 4)))
bestmod_4_svm_rad <- tune.out_4_svm_rad$best.model
#plot(bestmod_4_svm_rad, dat[train, ])
svm_plot(bestmod_4_svm_rad, dat[train, ])

Training error

svm_rad_error_train <- mean(summary(bestmod_4_svm_rad)$fitted != y[train])
error_train <- c(error_train, "svm (radial)" = svm_rad_error_train)

Test Error

ypred <- predict(bestmod_4_svm_rad, dat[test, ])
table(predict = ypred, truth = dat[test, "y"])
       truth
predict -1  1
     -1 11  1
     1   0  8
svm_rad_error_test <- mean(ypred != y[test])
error_test <- c(error_test, "svm (radial)" = svm_rad_error_test)

Summary of Errors

sort(error_train)
svm (radial)  svm (d = 2)  svm (d = 3)          svc 
      0.0125       0.2750       0.3500       0.4875 
sort(error_test)
svm (radial)  svm (d = 2)  svm (d = 3)          svc 
        0.05         0.25         0.40         0.55 

The SVM with radial kernel has the best training and test errors. This time, with a more complex decision boundary, both of the SVM’s with polynomial kernels outperformed the linear support vector classifier.


Exercise 5

  (a)

Generate a data set with \(n = 500\) and \(p = 2\), such that the observations belong to two classes with a quadratic decision boundary between them:

set.seed(1)
x1 <- runif(500) - 0.5
x2 <- runif(500) - 0.5
y <- 1*((x1^2 - x2^2) > 0)
df <- data.frame(x1, x2, y = as.factor(y)) 

  (b)

Plot the observations, colored according to their class labels:

g0 <- ggplot(df) +
  geom_point(aes(x1, x2, group = y, color = y)) +
  theme_bw() +
  ggtitle("True Class Labels") +
  theme(plot.title = element_text(hjust = 0.5)) +
  scale_color_discrete(name = "True Class")
g0

  (c)

Use all of the data as the training data

Fit a logistic regression model to the data, using \(X_1\) and \(X_2\) as predictors:

logreg <- glm(y ~ x1 + x2, data = df, family = "binomial") 
probs <- predict(logreg, newdata = df, type = "response")
preds <- rep(0, 500)
preds[probs > 0.5] <- 1

  (d)

Apply this model to the training data in order to obtain a predicted class label for each training observation. Plot the observations, colored according to the predicted class labels. The decision boundary should be linear:

df$logreg_preds <- as.factor(preds)
g1 <- ggplot(df) +
  geom_point(aes(x1, x2, group = logreg_preds, color = logreg_preds)) +
  theme_bw() +
  scale_color_discrete(name = "Pred. Class") + 
  ggtitle("Logistic Regression: y ~ x1 + x2") +
  theme(plot.title = element_text(hjust = 0.5))
cowplot::plot_grid(g0, g1, nrow = 1)

  (e)

Now fit a logistic regression model to the data using non-linear functions of \(X_1\) and \(X_2\) as predictors:

formulas <- c("y ~ I(x1^2) + I(x2^2)",
              "y ~ I(x1^0.5) + I(x2^0.5)",
              "y ~ x1 + x2 + I(x1^2) + I(x2^2)",
              "y ~ x1 + x2 + I(x1^0.5) + I(x2^0.5)",
              "y ~ x1 + x2 + I(x1^2) + I(x2^2) + I(x1 * x2)",
              "y ~ x1 + x2 + I(x1^0.5) + I(x2^0.5) + I(x1 * x2)"
)

logregs <- map(formulas, ~glm(as.formula(.x), data = df, family = "binomial"))
probs <- map(logregs, ~predict(.x, newdata = df, type = "response"))
preds <- vector("list", length(formulas))
preds <- map(1:length(formulas), function(x) preds[[x]] = rep(0, 500))
for(i in 1:length(formulas)) {
  preds[[i]][probs[[i]] > 0.5] <- 1
}

  (f)

With the models involving the squares of the predictors the predicted results look quite close to the true values. The models involving the square roots do not predict the classes well:

G2 <- vector("list", length(formulas))
for(i in 1:length(formulas)) {
  df_ <- data.frame(x1, x2, preds = as.factor(preds[[i]]))
  G2[[i]] <- ggplot(df_) +
                  geom_point(aes(x1, x2,
                                 group = preds,
                                 color = preds)) +
                  ggtitle(label = paste0(formulas[i])) +
                  theme_bw() +
                  theme(plot.title = element_text(hjust = 0.5)) +
    scale_color_discrete(name = "Pred. Class")
}

cowplot::plot_grid(plotlist = G2, nrow = 3)

  (g)

Fit a support vector classifier to the data with \(X_1\) and \(X_2\) as predictors:

svc.out <- tune(svm, y ~ ., data = df, kernel = "linear", ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100)))
svc <- svc.out$best.model
preds <- predict(svc, df)
df_ <- data.frame(x1, x2, preds = as.factor(preds))
g3 <- ggplot(df_) +
  geom_point(aes(x1, x2,
             group = preds,
             color = preds)) +
      ggtitle("Support Vector Classifier") +
      theme_bw() +
      theme(plot.title = element_text(hjust = 0.5)) +
      scale_color_discrete(name = "Pred. Class")
cowplot::plot_grid(g0, g3, nrow = 1)

  (h)

Fit a SVM using a non-linear kernel to the data.

Support vector machine with polynomial kernel, \(d\) = 2

svm.out <- tune(svm, y ~ ., data = df, kernel = "polynomial", degree = 2, ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100)))
svm1 <- svm.out$best.model
preds <- predict(svm1, df)
df_ <- data.frame(x1, x2, preds = as.factor(preds))
g4 <- ggplot(df_) +
  geom_point(aes(x1, x2,
             group = preds,
             color = preds)) +
      ggtitle("Support Vector Machine - Polynomial Kernel (d = 2)") +
      theme_bw() +
      theme(plot.title = element_text(hjust = 0.5, size = 10)) +
      scale_color_discrete(name = "Pred. Class")
cowplot::plot_grid(g0, g4, nrow = 1)

Support vector machine with radial kernel

svm.out2 <- tune(svm, y ~ ., data = df, kernel = "radial", degree = 2, ranges = list(cost = c (0.001, 0.01, 0.1, 1, 5, 10, 100), gamma = c(0.5, 1, 2, 3, 4)))
svm_rad <- svm.out$best.model
preds <- predict(svm_rad, df)
df_ <- data.frame(x1, x2, preds = as.factor(preds))
g5 <- ggplot(df_) +
  geom_point(aes(x1, x2,
             group = preds,
             color = preds)) +
      ggtitle("Support Vector Machine - Radial Kernel") +
      theme_bw() +
      theme(plot.title = element_text(hjust = 0.5, size = 12)) +
      scale_color_discrete(name = "Pred. Class")
cowplot::plot_grid(g0, g5, nrow = 1)

  (i)

The logistic regression model with linear combination of the variables and the support vector classifier both performed poorly. The logistic regression model with non-linear transformations of the variables, as well as support vector machines with polynomial and radial kernels all performed well.

g2 <- G2[[1]] + ggtitle("Logistic Regression: y ~ I(x1^2) + I(x2^2)")
cowplot::plot_grid(g0, g1, g2, g3, g4, g5, nrow = 3)


Exercise 6

It’s hard to figure out exactly what the best type of data is for this question. Most of the data sets tried result in zero test error as the cost increases. Using the below data set with a modest \(n\) of 100 seems to work for what the question asks, i.e. the test error gets to a minimum before rising again as the cost increases.

  (a)

# Prelim:
set.seed(1)

# Data:
n <- 100
x1 <- runif(n, max = 0.3, min = -0.3)
x2 <- rnorm(n, sd = 1)
y <- ifelse(-0.2 * x1 + x2 > 0, 1, -1)
df <- data.frame(x1, x2, y = as.factor(y))

# Train/Test:
train <- sample(n, 4*n/5)
test <- -train

# Plot:
ggplot(df) +
  geom_point(aes(x1, x2, group = y, color = y)) +
  theme_bw() +
  ggtitle("True Class Labels") +
  theme(plot.title = element_text(hjust = 0.5)) +
  scale_color_discrete(name = "True Class", breaks = c(1, -1))

  (b) and (c)

Generate support vector classifiers via cross validation using a range of values for cost (use all of the data for CV, then we will use the training/test splits in the next section):

costs <- c (0.001, 0.01, 0.1, 1, 5, 10, 100, 1e3, 1e4, 1e5)
svc.out <- tune(svm, y ~ ., data = df, kernel = "linear", ranges = list(cost = costs))
svc.cv.error <- svc.out$performances$error # extract the CV errors
svc.cv.error
 [1] 0.44 0.25 0.05 0.06 0.06 0.05 0.04 0.03 0.02 0.02

The training and test errors can be obtained by training SVC models using a range of values for cost and then making predictions on the training and test data respectively:

svc.train.error <- vector("double", length(costs))
svc.test.error <- vector("double", length(costs))
G <- vector("list", length(costs))
for(i in 1:length(costs)) {
  svc <- svm(y ~ ., data = df[train, ], kernel = "linear", cost = costs[i])
  G[[i]] <- svm_plot(svc, df[train, ]) + ggtitle(str_c("cost: ", costs[i]))
  
  # Training Error:
  preds <- predict(svc, df[train, ])
  train.error <- mean(preds != y[train])
  svc.train.error[i] <- train.error
  
  # Test Error:
  preds <- predict(svc, df[test, ])
  test.error <- mean(preds != y[test])
  svc.test.error[i] <- test.error
}

svc.train.error
 [1] 0.4375 0.2500 0.1000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
svc.test.error
 [1] 0.45 0.35 0.00 0.05 0.05 0.05 0.05 0.05 0.05 0.05
plot_grid(plotlist = G, nrow = 5)

Plot the CV, training, and test errors:

library(latex2exp)
svc.errors <- data.frame(cost = log10(costs),
                         cv.error = svc.cv.error,
                         train.error = svc.train.error,
                         test.error = svc.test.error)

# see https://stackoverflow.com/a/50496899 and https://stackoverflow.com/a/10355844 for making legend
ggplot(svc.errors) +
  geom_line(aes(cost, cv.error, color = "CV")) +
  geom_line(aes(cost, train.error, color = "Train")) +
  geom_line(aes(cost, test.error, color = "Test")) +
  geom_hline(aes(yintercept = min(svc.test.error)), color = "grey30", linetype = "dashed") +
  scale_color_manual(name = "Error Rate", breaks = c("Test", "Train", "CV"), values = c("Test" = "#00BA38", "CV" = "#F8766D", "Train" = "#619CFF")) +
  #scale_color_discrete(name = NULL, labels = c("CV Error", "Test Error", "Training Error")) +
  labs(title = "Comparison of CV, Training and Test Error Rates",
       x = TeX("Log_{10}(Cost)"),
       y = "Error Rate") +
  theme_bw() +
  theme(plot.title = element_text(hjust = 0.5),
        legend.position = c(0.97, 0.95), legend.justification = c(1, 1))

  (d)

The error rates approach zero as the cost increases from small values towards 1. Then, the test error starts to rise again, suggesting that a lower value for cost is better, even though the training error is zero for larger values.


Exercise 7

View data:

Auto

Summary:

summary(Auto)
      mpg          cylinders      displacement     horsepower        weight      acceleration        year           origin     
 Min.   : 9.00   Min.   :3.000   Min.   : 68.0   Min.   : 46.0   Min.   :1613   Min.   : 8.00   Min.   :70.00   Min.   :1.000  
 1st Qu.:17.00   1st Qu.:4.000   1st Qu.:105.0   1st Qu.: 75.0   1st Qu.:2225   1st Qu.:13.78   1st Qu.:73.00   1st Qu.:1.000  
 Median :22.75   Median :4.000   Median :151.0   Median : 93.5   Median :2804   Median :15.50   Median :76.00   Median :1.000  
 Mean   :23.45   Mean   :5.472   Mean   :194.4   Mean   :104.5   Mean   :2978   Mean   :15.54   Mean   :75.98   Mean   :1.577  
 3rd Qu.:29.00   3rd Qu.:8.000   3rd Qu.:275.8   3rd Qu.:126.0   3rd Qu.:3615   3rd Qu.:17.02   3rd Qu.:79.00   3rd Qu.:2.000  
 Max.   :46.60   Max.   :8.000   Max.   :455.0   Max.   :230.0   Max.   :5140   Max.   :24.80   Max.   :82.00   Max.   :3.000  
                                                                                                                               
                 name    
 amc matador       :  5  
 ford pinto        :  5  
 toyota corolla    :  5  
 amc gremlin       :  4  
 amc hornet        :  4  
 chevrolet chevette:  4  
 (Other)           :365  
Auto$origin <- as.factor(Auto$origin)
Auto$year <- factor(Auto$year, ordered = TRUE)
head(Auto)

  (a)

Create a binary variable that takes on a 1 for cars with gas mileage above the median, and a 0 for cars with gas mileage below the median:

Auto$med01 <- as.factor(Auto$mpg > median(Auto$mpg))
Auto <- Auto[ , -1]
summary(Auto$med01)
FALSE  TRUE 
  196   196 

  (b)

Fit a support vector classifier to the data with various values of cost, in order to predict whether a car gets high or low gas mileage:

set.seed(1)
costs <- c (0.001, 0.01, 0.1, 1, 5, 10, 50, 100, 250, 500, 1e3, 5e3, 1e4, 5e4, 1e5)
svc.out <- tune(svm, med01 ~ ., data = Auto, kernel = "linear", ranges = list(cost = costs))
svc.cv.error <- svc.out$performances$error # extract the CV errors
svc.cv.error
 [1] 0.18141026 0.10211538 0.09955128 0.09192308 0.09442308 0.09955128 0.14032051 0.14288462 0.15570513 0.15570513 0.15570513
[12] 0.15570513 0.15570513 0.15570513 0.15570513

Plot CV errors:

ggplot(data.frame(cost = log10(costs), cv.error = svc.cv.error)) +
  geom_line(aes(cost, cv.error), color = ISLR_orange) +
  labs(title = "CV Error Rate as Function of Cost",
       x = TeX("Log_{10}(Cost)"),
       y = "CV Error Rate") +
  theme_bw() +
  theme(plot.title = element_text(hjust = 0.5))

  (c)

Now repeat (b), this time using SVMs with radial and polynomial basis kernels, with different values of gamma and degree and cost.

Polynomial Kernel

set.seed(1)
costs <- c (0.001, 0.01, 0.1, 1, 5, 10, 50, 100, 250, 500, 1e3, 5e3, 1e4, 5e4, 1e5)
degrees <- c(2, 3, 4, 5)
svc.out.poly <- tune(svm, med01 ~ ., data = Auto, kernel = "polynomial", ranges = list(degree = degrees, cost = costs)) # first variable in ranges is the rows in below matrix
svc.poly.cv.error <- svc.out.poly$performances$error # extract the CV errors
round(matrix(svc.poly.cv.error, nrow = length(degrees)), 3)
      [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10] [,11] [,12] [,13] [,14] [,15]
[1,] 0.551 0.551 0.551 0.551 0.551 0.549 0.352 0.281 0.250 0.228 0.135 0.097 0.082 0.089 0.089
[2,] 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.454 0.368 0.312 0.276 0.255 0.258 0.123 0.120
[3,] 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.498 0.470 0.383 0.350
[4,] 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.551 0.503 0.493

Plot CV errors:

dat_ <- data.frame(cbind(cost = log10(costs), t(matrix(svc.poly.cv.error, nrow = length(degrees))))) %>% 
        gather(key = "degree", value = "cv.error", V2:V5) %>% 
        mutate(degree = factor(str_replace(degree, "V", "degree: ")))

ggplot(dat_) +
  geom_line(aes(cost, cv.error, color = degree)) +
  labs(title = "Polynomial Kernel - CV Error Rate as Function of Cost",
       x = TeX("Log_{10}(Cost)"),
       y = "CV Error Rate") +
  ggsci::scale_color_d3() +
  theme_bw() +
  theme(plot.title = element_text(hjust = 0.5))

Radial Kernel

set.seed(1)
costs <- c(0.001, 0.01, 0.1, 1, 5, 10, 50, 100, 250, 500, 1e3, 5e3, 1e4, 5e4, 1e5)
gammas = c(0.01, 0.05, 0.1, 0.5)
svc.out.rad <- tune(svm, med01 ~ ., data = Auto, kernel = "polynomial", ranges = list(gamma = gammas, cost = costs)) # first variable in ranges is the rows in below matrix
svc.rad.cv.error <- svc.out.rad$performances$error # extract the CV errors
round(matrix(svc.rad.cv.error, nrow = length(gammas)), 3)
      [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10] [,11] [,12] [,13] [,14] [,15]
[1,] 0.551 0.551 0.551 0.551 0.408 0.350 0.260 0.261 0.258 0.240 0.192 0.120 0.097 0.084 0.082
[2,] 0.551 0.551 0.337 0.255 0.230 0.143 0.110 0.097 0.084 0.084 0.079 0.079 0.079 0.079 0.079
[3,] 0.551 0.350 0.261 0.192 0.120 0.097 0.084 0.082 0.079 0.079 0.079 0.079 0.079 0.079 0.079
[4,] 0.255 0.143 0.097 0.079 0.079 0.079 0.079 0.079 0.079 0.079 0.079 0.079 0.079 0.079 0.079

Plot CV errors:

dat_ <- data.frame(cbind(cost = log10(costs), t(matrix(svc.rad.cv.error, nrow = length(gammas))))) %>% 
        gather(key = "gamma", value = "cv.error", V2:V5) %>% 
        mutate(gamma = str_c("gamma: ", factor(gammas[as.numeric(str_remove(gamma, "V")) - 1]))) # factor to make it a discrete var in ggplot()

ggplot(dat_) +
  geom_line(aes(cost, cv.error, color = gamma)) +
  labs(title = "Radial Kernel - CV Error Rate as Function of Cost",
       x = TeX("Log_{10}(Cost)"),
       y = "CV Error Rate") +
  ggsci::scale_color_d3() +
  theme_bw() +
  theme(plot.title = element_text(hjust = 0.5))

  (d)

A support vector machine with a linear kernel and cost = 0.1 performs well, with a CV error of 0.087

A support vector machine with a polynomial kernel of degree three and also achieves a low CV error of 0.08. However the cost is very large at 100,000.

A support vector machine with a radial kernel and parameters of cost = 1 and gamma = 0.5 has the lowest CV error at 0.089. Other radial kernel SVM’s with very large cost values also have an equally low CV error, but a gamma value of 0.5 performs well with lower cost which would likely overfit less than the other models.


Exercise 8

View data:

head(OJ)

Summary:

summary(OJ)
 Purchase WeekofPurchase     StoreID        PriceCH         PriceMM          DiscCH            DiscMM         SpecialCH     
 CH:653   Min.   :227.0   Min.   :1.00   Min.   :1.690   Min.   :1.690   Min.   :0.00000   Min.   :0.0000   Min.   :0.0000  
 MM:417   1st Qu.:240.0   1st Qu.:2.00   1st Qu.:1.790   1st Qu.:1.990   1st Qu.:0.00000   1st Qu.:0.0000   1st Qu.:0.0000  
          Median :257.0   Median :3.00   Median :1.860   Median :2.090   Median :0.00000   Median :0.0000   Median :0.0000  
          Mean   :254.4   Mean   :3.96   Mean   :1.867   Mean   :2.085   Mean   :0.05186   Mean   :0.1234   Mean   :0.1477  
          3rd Qu.:268.0   3rd Qu.:7.00   3rd Qu.:1.990   3rd Qu.:2.180   3rd Qu.:0.00000   3rd Qu.:0.2300   3rd Qu.:0.0000  
          Max.   :278.0   Max.   :7.00   Max.   :2.090   Max.   :2.290   Max.   :0.50000   Max.   :0.8000   Max.   :1.0000  
   SpecialMM         LoyalCH          SalePriceMM     SalePriceCH      PriceDiff       Store7      PctDiscMM     
 Min.   :0.0000   Min.   :0.000011   Min.   :1.190   Min.   :1.390   Min.   :-0.6700   No :714   Min.   :0.0000  
 1st Qu.:0.0000   1st Qu.:0.325257   1st Qu.:1.690   1st Qu.:1.750   1st Qu.: 0.0000   Yes:356   1st Qu.:0.0000  
 Median :0.0000   Median :0.600000   Median :2.090   Median :1.860   Median : 0.2300             Median :0.0000  
 Mean   :0.1617   Mean   :0.565782   Mean   :1.962   Mean   :1.816   Mean   : 0.1465             Mean   :0.0593  
 3rd Qu.:0.0000   3rd Qu.:0.850873   3rd Qu.:2.130   3rd Qu.:1.890   3rd Qu.: 0.3200             3rd Qu.:0.1127  
 Max.   :1.0000   Max.   :0.999947   Max.   :2.290   Max.   :2.090   Max.   : 0.6400             Max.   :0.4020  
   PctDiscCH       ListPriceDiff       STORE      
 Min.   :0.00000   Min.   :0.000   Min.   :0.000  
 1st Qu.:0.00000   1st Qu.:0.140   1st Qu.:0.000  
 Median :0.00000   Median :0.240   Median :2.000  
 Mean   :0.02731   Mean   :0.218   Mean   :1.631  
 3rd Qu.:0.00000   3rd Qu.:0.300   3rd Qu.:3.000  
 Max.   :0.25269   Max.   :0.440   Max.   :4.000  

  (a)

Create a training set containing a random sample of 800 observations, and a test set containing the remaining observations:

# Prelims:
set.seed(1)

# Data:
df <- OJ

# Train/Test:
train <- sample(1:nrow(OJ), 800)
test <- -train

  (b)

Fit a support vector classifier to the training data using cost = 0.01, with Purchase as the response and the other variables as predictors:

svc_8 <- svm(Purchase ~ . , data = df[train, ], kernel = "linear", cost = 0.01)
summary(svc_8)

Call:
svm(formula = Purchase ~ ., data = df[train, ], kernel = "linear", cost = 0.01)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  linear 
       cost:  0.01 

Number of Support Vectors:  435

 ( 219 216 )


Number of Classes:  2 

Levels: 
 CH MM

  (c)

Training error:

svc_8.train.error <- mean(predict(svc_8, df[train, ]) != df$Purchase[train])
svc_8.train.error
[1] 0.175

Test error:

svc_8.test.error <- mean(predict(svc_8, df[test, ]) != df$Purchase[test])
svc_8.test.error
[1] 0.1777778

  (d)

Use the tune() function to select an optimal cost. Consider values in the range 0.01 to 10.

set.seed(1)
costs <- c (0.01, 0.05, 0.1, 0.25, 0.5, 1, 2, 5, 10)
svc.out_8 <- tune(svm, Purchase ~ ., data = df[train, ], kernel = "linear", ranges = list(cost = costs))
svc_8.cv.error <- svc.out_8$performances$error # extract the CV errors
svc_8.cv.error
[1] 0.17625 0.17625 0.17250 0.17125 0.16875 0.17500 0.17250 0.17250 0.17375

Plot:

ggplot(data.frame(cost = log10(costs), cv.error = svc_8.cv.error)) +
  geom_line(aes(cost, cv.error), color = ISLR_orange) +
  labs(title = "Linear Kernel - CV Error Rate as Function of Cost",
       x = TeX("Log_{10}(Cost)"),
       y = "CV Error Rate") +
  theme_bw() +
  theme(plot.title = element_text(hjust = 0.5))

  (e)

The training and test errors can be obtained by training SVC models using a range of values for cost and then making predictions on the training and test data respectively:

set.seed(1)
svc_8.train.error <- vector("double", length(costs))
svc_8.test.error <- vector("double", length(costs))
for(i in 1:length(costs)) {
  svc <- svm(Purchase ~ ., data = df[train, ], kernel = "linear", cost = costs[i])
  
  # Training Error:
  preds <- predict(svc, df[train, ])
  train.error <- mean(preds != df$Purchase[train])
  svc_8.train.error[i] <- train.error
  
  # Test Error:
  preds <- predict(svc, df[test, ])
  test.error <- mean(preds != df$Purchase[test])
  svc_8.test.error[i] <- test.error
}

svc_8.train.error
[1] 0.17500 0.17000 0.16500 0.16500 0.16500 0.16375 0.16500 0.16625 0.16375
svc_8.test.error
[1] 0.1777778 0.1629630 0.1629630 0.1592593 0.1555556 0.1555556 0.1518519 0.1555556 0.1481481

Plot the CV, training, and test errors:

library(latex2exp)
svc_8.errors <- data.frame(cost = log10(costs),
                         cv.error = svc_8.cv.error,
                         train.error = svc_8.train.error,
                         test.error = svc_8.test.error)

# see https://stackoverflow.com/a/50496899 and https://stackoverflow.com/a/10355844 for making legend
g1 <- ggplot(svc_8.errors) +
  geom_line(aes(cost, cv.error, color = "CV")) +
  geom_line(aes(cost, train.error, color = "Train")) +
  geom_line(aes(cost, test.error, color = "Test")) +
  scale_color_manual(name = "Error Rate", breaks = c("Test", "Train", "CV"), values = c("Test" = "#00BA38", "CV" = "#F8766D", "Train" = "#619CFF")) +
  #scale_color_discrete(name = NULL, labels = c("CV Error", "Test Error", "Training Error")) +
  labs(title = "Linear Kernel - Comparison of CV, Training and Test Error Rates",
       x = TeX("Log_{10}(Cost)"),
       y = "Error Rate") +
  theme_bw() +
  theme(plot.title = element_text(hjust = 0.5),
        legend.position = c(0.97, 0.95), legend.justification = c(1, 1))
g1

The training error seems to be higher than the test error.

  (f)

Radial Kernel

set.seed(1)
svm_8_rad <- svm(Purchase ~ . , data = df[train, ], kernel = "radial", cost = 0.01)
summary(svm_8_rad)

Call:
svm(formula = Purchase ~ ., data = df[train, ], kernel = "radial", cost = 0.01)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  radial 
       cost:  0.01 

Number of Support Vectors:  634

 ( 319 315 )


Number of Classes:  2 

Levels: 
 CH MM

Training error:

svm_8_rad.train.error <- mean(predict(svm_8_rad, df[train, ]) != df$Purchase[train])
svm_8_rad.train.error
[1] 0.39375

Test error:

svm_8_rad.test.error <- mean(predict(svm_8_rad, df[test, ]) != df$Purchase[test])
svm_8_rad.test.error
[1] 0.3777778

Use CV:

set.seed(1)
svm.out_8_rad <- tune(svm, Purchase ~ ., data = df[train, ], kernel = "radial", ranges = list(cost = costs))
svm_8_rad.cv.error <- svm.out_8_rad$performances$error # extract the CV errors
svm_8_rad.cv.error
[1] 0.39375 0.20250 0.18625 0.18000 0.16750 0.17125 0.17750 0.18000 0.18625

Plot CV error:

ggplot(data.frame(cost = log10(costs), cv.error = svm_8_rad.cv.error)) +
  geom_line(aes(cost, cv.error), color = ISLR_orange) +
  labs(title = "Radial Kernel - CV Error Rate as Function of Cost",
       x = TeX("Log_{10}(Cost)"),
       y = "CV Error Rate") +
  theme_bw() +
  theme(plot.title = element_text(hjust = 0.5))

The training and test errors can be obtained by training SVM models using a range of values for cost and then making predictions on the training and test data respectively:

set.seed(1)
svm_8_rad.train.error <- vector("double", length(costs))
svm_8_rad.test.error <- vector("double", length(costs))
for(i in 1:length(costs)) {
  svm_8 <- svm(Purchase ~ ., data = df[train, ], kernel = "radial", cost = costs[i])
  
  # Training Error:
  preds <- predict(svm_8, df[train, ])
  train.error <- mean(preds != df$Purchase[train])
  svm_8_rad.train.error[i] <- train.error
  
  # Test Error:
  preds <- predict(svm_8, df[test, ])
  test.error <- mean(preds != df$Purchase[test])
  svm_8_rad.test.error[i] <- test.error
}

svm_8_rad.train.error
[1] 0.39375 0.18250 0.17375 0.16000 0.14750 0.15125 0.14750 0.14625 0.14500
svm_8_rad.test.error
[1] 0.3777778 0.2333333 0.2037037 0.1962963 0.1777778 0.1851852 0.1814815 0.1777778 0.1851852

Plot the CV, training, and test errors:

library(latex2exp)
svm_8_rad.errors <- data.frame(cost = log10(costs),
                         cv.error = svm_8_rad.cv.error,
                         train.error = svm_8_rad.train.error,
                         test.error = svm_8_rad.test.error)

# see https://stackoverflow.com/a/50496899 and https://stackoverflow.com/a/10355844 for making legend
g2 <- ggplot(svm_8_rad.errors) +
  geom_line(aes(cost, cv.error, color = "CV")) +
  geom_line(aes(cost, train.error, color = "Train")) +
  geom_line(aes(cost, test.error, color = "Test")) +
  scale_color_manual(name = "Error Rate", breaks = c("Test", "Train", "CV"), values = c("Test" = "#00BA38", "CV" = "#F8766D", "Train" = "#619CFF")) +
  #scale_color_discrete(name = NULL, labels = c("CV Error", "Test Error", "Training Error")) +
  labs(title = "Radial Kernel - Comparison of CV, Training and Test Error Rates",
       x = TeX("Log_{10}(Cost)"),
       y = "Error Rate") +
  theme_bw() +
  theme(plot.title = element_text(hjust = 0.5),
        legend.position = c(0.97, 0.95), legend.justification = c(1, 1))
g2

With the radial kernel, the training error is lower than the test error.

  (g)

Polynomial Kernel

set.seed(1)
svm_8_poly <- svm(Purchase ~ . , data = df[train, ], kernel = "polynomial", degree = 2, cost = 0.01)
summary(svm_8_poly)

Call:
svm(formula = Purchase ~ ., data = df[train, ], kernel = "polynomial", degree = 2, cost = 0.01)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  polynomial 
       cost:  0.01 
     degree:  2 
     coef.0:  0 

Number of Support Vectors:  636

 ( 321 315 )


Number of Classes:  2 

Levels: 
 CH MM

Training error:

svm_8_poly.train.error <- mean(predict(svm_8_poly, df[train, ]) != df$Purchase[train])
svm_8_poly.train.error
[1] 0.3725

Test error:

svm_8_poly.test.error <- mean(predict(svm_8_poly, df[test, ]) != df$Purchase[test])
svm_8_poly.test.error
[1] 0.3666667

Use CV:

set.seed(1)
svm.out_8_poly <- tune(svm, Purchase ~ ., data = df[train, ], kernel = "polynomial", degree = 2, ranges = list(cost = costs))

Plot CV error:

ggplot(data.frame(cost = log10(costs), cv.error = svm_8_poly.cv.error)) +
  geom_line(aes(cost, cv.error), color = ISLR_orange) +
  labs(title = "Polynomial Kernel (d = 2) - CV Error Rate as Function of Cost",
       x = TeX("Log_{10}(Cost)"),
       y = "CV Error Rate") +
  theme_bw() +
  theme(plot.title = element_text(hjust = 0.5))

The training and test errors can be obtained by training SVC models using a range of values for cost and then making predictions on the training and test data respectively:

set.seed(1)
svm_8_poly.train.error <- vector("double", length(costs))
svm_8_poly.test.error <- vector("double", length(costs))
for(i in 1:length(costs)) {
  svm_8 <- svm(Purchase ~ ., data = df[train, ], kernel = "polynomial", degree = 2, cost = costs[i])
  
  # Training Error:
  preds <- predict(svm_8, df[train, ])
  train.error <- mean(preds != df$Purchase[train])
  svm_8_poly.train.error[i] <- train.error
  
  # Test Error:
  preds <- predict(svm_8, df[test, ])
  test.error <- mean(preds != df$Purchase[test])
  svm_8_poly.test.error[i] <- test.error
}

svm_8_poly.train.error
[1] 0.37250 0.33125 0.30625 0.19125 0.18750 0.18250 0.16000 0.15500 0.15000
svm_8_poly.test.error
[1] 0.3666667 0.3074074 0.2962963 0.2333333 0.2259259 0.2222222 0.2111111 0.1814815 0.1888889

Plot the CV, training, and test errors:

library(latex2exp)
svm_8_poly.errors <- data.frame(cost = log10(costs),
                         cv.error = svm_8_poly.cv.error,
                         train.error = svm_8_poly.train.error,
                         test.error = svm_8_poly.test.error)

# see https://stackoverflow.com/a/50496899 and https://stackoverflow.com/a/10355844 for making legend
g3 <- ggplot(svm_8_poly.errors) +
  geom_line(aes(cost, cv.error, color = "CV")) +
  geom_line(aes(cost, train.error, color = "Train")) +
  geom_line(aes(cost, test.error, color = "Test")) +
  scale_color_manual(name = "Error Rate", breaks = c("Test", "Train", "CV"), values = c("Test" = "#00BA38", "CV" = "#F8766D", "Train" = "#619CFF")) +
  #scale_color_discrete(name = NULL, labels = c("CV Error", "Test Error", "Training Error")) +
  labs(title = "Polynomial Kernel (d = 2) - Comparison of CV, Training and Test Error Rates",
       x = TeX("Log_{10}(Cost)"),
       y = "Error Rate") +
  theme_bw() +
  theme(plot.title = element_text(hjust = 0.5),
        legend.position = c(0.97, 0.95), legend.justification = c(1, 1))
g3

With the radial kernel, the training error is lower than the test error.

  (h)

Comparison of three kernels:

plot_grid(plotlist = list(g1 + ggtitle("Linear") + scale_y_continuous(limits = c(0.14, 0.4), breaks = seq(0.1, 0.4, by = 0.05)),
                          g2 + ggtitle("Radial") + scale_y_continuous(limits = c(0.14, 0.4), breaks = seq(0.1, 0.4, by = 0.05)) + theme(axis.title.y = element_blank()),
                          g3 + ggtitle("Polynomial") + scale_y_continuous(limits = c(0.14, 0.4), breaks = seq(0.1, 0.4, by = 0.05)) + theme(axis.title.y = element_blank())), nrow = 1)


  1. James G, Witten D, Hastie T, Tibshirani R (2013). An Introduction to Statistical Learning: with Applications in R. Springer, 1st edition.↩︎

LS0tCnRpdGxlOiAiQW4gSW50cm9kdWN0aW9uIHRvIFN0YXRpc3RpY2FsIExlYXJuaW5nICgyMDEzKSIKc3VidGl0bGU6ICJTb2x1dGlvbnMgdG8gQXBwbGllZCBFeGVyY2lzZXMiCmF1dGhvcjogImJ5IEJyaWFuIEhhc3NldHQiCm91dHB1dDogCiAgaHRtbF9ub3RlYm9vazogCiAgICB0b2M6IHllcwogICAgdG9jX2RlcHRoOiAyCi0tLQoKIyBDaGFwdGVyIDkgU3VwcG9ydCBWZWN0b3IgTWFjaGluZXMKClRoaXMgbm90ZWJvb2sgaXMgYSByb3VnaCBvdXRsaW5lIG9mIHNvbHV0aW9ucyB0byB0aGUgYXBwbGllZCBleGVyY2lzZXMgaW4gQ2hhcHRlciA5IG9mICoqQW4gSW50cm9kdWN0aW9uIHRvIFN0YXRpc3RpY2FsIExlYXJuaW5nKiogKEphbWVzIGV0IGFsLiAoMjAxMylbXjFdKS4KClteMV06IEphbWVzIEcsIFdpdHRlbiBELCBIYXN0aWUgVCwgVGlic2hpcmFuaSBSICgyMDEzKS4gKkFuIEludHJvZHVjdGlvbiB0byBTdGF0aXN0aWNhbCBMZWFybmluZzogd2l0aCBBcHBsaWNhdGlvbnMgaW4gUiouIFNwcmluZ2VyLCAxc3QgZWRpdGlvbi4KCiMjIFNldHVwCmBgYHtyIHNldHVwLCBtZXNzYWdlPUZBTFNFfQpsaWJyYXJ5KElTTFIpCmxpYnJhcnkoZTEwNzEpCmxpYnJhcnkoY293cGxvdCkKbGlicmFyeShsYXRleDJleHApCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KHBhdGNod29yaykKdGhlbWVfc2V0KHRoZW1lX2J3KCkpCgojIEdpdmVuIGEgZmlsZW5hbWUsIHJldHVybiB0aGUgZmlsZXBhdGguIERlZmF1bHQgZm9sZGVyIGlzIHRoZSBgZGF0YWAgZm9sZGVyIGluIHRoZSBjdXJyZW50IHdvcmtpbmcgZGlyZWN0b3J5LgpnZXRfcGF0aCA8LSBmdW5jdGlvbihmaWxlbmFtZSkgewogIHN0cl9jKGdldHdkKCksICJkYXRhIiwgZmlsZW5hbWUsIHNlcCA9ICIvIikKfQoKIyBMb2FkIG15IGZ1bmN0aW9uczoKc291cmNlKCIvaG9tZS9icmlhbi9SL2Rpci9VdGlsL2JoX2Z1bmN0aW9ucy5SIikKCiMgQ29sb3JzOgpJU0xSX2JsdWUgPC0gIiMxNzZGQzAiCklTTFJfYnJvd24gPC0gIiM5NDM0MEUiCklTTFJfbGlnaHRibHVlIDwtICIjNjhBNURCIgpJU0xSX29yYW5nZSA8LSAiI0NDNTMxOCIKCiMgRnVuY3Rpb25zIGZvciBwbG90dGluZyBgc3ZtYCBvYmplY3RzOgpkaXN0MnBvaW50IDwtIGZ1bmN0aW9uKGNvZWYsIHApIHsKICBkaXN0IDwtIChjb2VmWzJdKnBbMV0gKyBjb2VmWzNdKnBbMl0gK2NvZWZbMV0pIC8gc3FydChjb2VmWzJdXjIgKyBjb2VmWzNdXjIpCiAgdW5uYW1lKGRpc3QpCn0KCnN2Y19tYXJnaW5zIDwtIGZ1bmN0aW9uKHN2YykgewogIHNsb3BlIDwtIC1jb2VmKHN2YylbM10vY29lZihzdmMpWzJdICMgc2xvcGUKICBpbnQwIDwtIC1jb2VmKHN2YylbMV0gIyBoeXBlcnBsYW5lIGludGVyY2VwdAogIHYxIDwtIHN2YyRTVlthcHBseShzdmMkU1YsIDEsIGZ1bmN0aW9uKHYpIGRpc3QycG9pbnQoY29lZihzdmMpLCB2KSkgJT4lIHdoaWNoLm1heCgpLCBdICMgc3VwcG9ydCB2ZWN0b3IgMQogIHYyIDwtIHN2YyRTVlthcHBseShzdmMkU1YsIDEsIGZ1bmN0aW9uKHYpIGRpc3QycG9pbnQoY29lZihzdmMpLCB2KSkgJT4lIHdoaWNoLm1pbigpLCBdICMgc3VwcG9ydCB2ZWN0b3IgMgoKICBpbnQxIDwtIHYxWzFdIC0gc2xvcGUqdjFbMl0gIyBpbnRlcmNlcHQgb2YgbWFyZ2luIDEKICBpbnQyIDwtIHYyWzFdIC0gc2xvcGUqdjJbMl0gIyBpbnRlcmNlcHQgb2YgbWFyZ2luIDIKCiAgYyhzbG9wZSwgaW50MCwgaW50MSwgaW50MikgJT4lIHVubmFtZSgpCn0KCnN2bV9wbG90IDwtIGZ1bmN0aW9uKHN2bSwgZGYpIHsKICBkYXQgPC0gZGYKICB4MSA8LSBkYXRbICwgMV0KICB4MiA8LSBkYXRbICwgMl0KICB5IDwtIGRhdFsgLCBuY29sKGRhdCldCiAgCiAgZ3JpZCA8LSBleHBhbmQuZ3JpZChzZXEobWluKHgxKSwgbWF4KHgxKSwgbGVuZ3RoLm91dCA9IDEwMCksCiAgICAgICAgICAgICAgICAgICAgICBzZXEobWluKHgyKSwgbWF4KHgyKSwgbGVuZ3RoLm91dCA9IDEwMCkpIAogIG5hbWVzKGdyaWQpIDwtIG5hbWVzKGRhdClbMToyXQogIHByZWRzIDwtIHByZWRpY3Qoc3ZtLCBncmlkKQogIGRhdF8gPC0gZGF0YS5mcmFtZShncmlkLCBwcmVkcykKICAKICBjb2xzIDwtIGMoJzEnID0gJyNmNTMyMjQnLCAnLTEnID0gJyMxYTZlZmYnKSAjIDEgOj0gcmVkLCAtMSA6PSBibHVlOyB0aHJlZSBzaGFkZXMgZGFya2VyIG9uIGh0dHBzOi8vd3d3Lnczc2Nob29scy5jb20vY29sb3JzL2NvbG9yc19waWNrZXIuYXNwCiAgdGlsZXMgPC0gYygnMScgPSAnI0Y4NzY2RCcsICctMScgPSAnIzYxOUNGRicpCiAgc2hhcGVzIDwtIGMoJ3N1cHBvcnQnID0gNCwgJ25vdHN1cHBvcnQnID0gMSkKICBkYXQkc3VwcG9ydCA8LSAnbm90c3VwcG9ydCcKICBkYXRbc3ZtJGluZGV4LCAnc3VwcG9ydCddIDwtICdzdXBwb3J0JwoKICBnIDwtIGdncGxvdChkYXRfLCBhZXMoeCA9IHgyLCB5ID0geDEpKSArCiAgICAgICAgICBnZW9tX3RpbGUoYWVzKGZpbGwgPSBwcmVkcyksIGNvbG9yID0gIndoaXRlIiwgYWxwaGEgPSAwLjMpICsgCiAgICAgICAgICBzY2FsZV9maWxsX21hbnVhbChuYW1lID0gIlByZWQuIENsYXNzIiwgdmFsdWVzID0gdGlsZXMpCiAgCiAgaWYoc3ZtJGtlcm5lbCA9PSAwKSB7ICMgaWYgbGluZWFyIGtlcm5lbCBhZGQgbWFyZ2lucwogICAgbWFyZ2lucyA8LSBzdmNfbWFyZ2lucyhzdm0pCiAgICBnIDwtIGcgKyAKICAgICAgICAgICNnZW9tX2FibGluZShhZXMoc2xvcGUgPSBtYXJnaW5zWzFdLCBpbnRlcmNlcHQgPSBtYXJnaW5zWzJdKSwgY29sID0gImdyZWVuIikgKyAjIGxpbmUgb2Ygc2VwYXJhdGlvbgogICAgICAgICAgZ2VvbV9hYmxpbmUoYWVzKHNsb3BlID0gbWFyZ2luc1sxXSwgaW50ZXJjZXB0ID0gbWFyZ2luc1s0XSksIGNvbCA9IGNvbHNbMV0pICsgIyAgMSA6PSByZWQKICAgICAgICAgIGdlb21fYWJsaW5lKGFlcyhzbG9wZSA9IG1hcmdpbnNbMV0sIGludGVyY2VwdCA9IG1hcmdpbnNbM10pLCBjb2wgPSBjb2xzWzJdKSAjIC0xIDo9IGJsdWUKICB9CgogIGcgPC0gZyArCiAgICAgICAgZ2VvbV9wb2ludChkYXRhID0gZGF0LCBhZXMoY29sb3IgPSB5LCBzaGFwZSA9IHN1cHBvcnQpLCBzaXplID0gMiwgc2hvdy5sZWdlbmQgPSBGQUxTRSkgKwogICAgICAgIHNjYWxlX2NvbG9yX21hbnVhbCh2YWx1ZXMgPSBjb2xzKSArCiAgICAgICAgc2NhbGVfc2hhcGVfbWFudWFsKHZhbHVlcyA9IHNoYXBlcykgKwogICAgICAgIHNjYWxlX3hfY29udGludW91cyhleHBhbmQgPSBjKDAsIDApKSArCiAgICAgICAgc2NhbGVfeV9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwgMCkpICsKICAgICAgICBndWlkZXMoZmlsbCA9IGd1aWRlX2xlZ2VuZChvdmVycmlkZS5hZXMgPSBsaXN0KGFscGhhID0gMSkpKSArCiAgICAgICAgdGhlbWVfYncoKSArCiAgICAgICAgZ2d0aXRsZSgnU1ZNIENsYXNzaWZpY2F0aW9uIFBsb3QnKSArCiAgICAgICAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpCiAgZwp9CgojIFJldHVybiB2ZWN0b3Igb2YgdGhlIG5hbWVzIG9mIG51bWVyaWMgY29sdW1ucyBpbiBhIGRhdGEgZnJhbWU6Cm51bWVyaWNfY29scyA8LSBmdW5jdGlvbihkZikgewogIGlzX251bWVyaWNfY29scyA8LSBtYXBfbGdsKGRmLCBpcy5udW1lcmljKQogIHJldHVybihuYW1lcyhkZilbaXNfbnVtZXJpY19jb2xzXSkKfQpgYGAKCiMjIEV4ZXJjaXNlIDQKCipHZW5lcmF0ZSBhIHNpbXVsYXRlZCB0d28tY2xhc3MgZGF0YSBzZXQgd2l0aCAxMDAgb2JzZXJ2YXRpb25zIGFuZCB0d28gZmVhdHVyZXMgaW4gd2hpY2ggdGhlcmUgaXMgYSB2aXNpYmxlIGJ1dCBub24tbGluZWFyIHNlcGFyYXRpb24gYmV0d2VlbiB0aGUgdHdvIGNsYXNzZXMuIFNob3cgdGhhdCBpbiB0aGlzIHNldHRpbmcsIGEgc3VwcG9ydCB2ZWN0b3IgbWFjaGluZSB3aXRoIGEgcG9seW5vbWlhbCBrZXJuZWwgKHdpdGggZGVncmVlIGdyZWF0ZXIgdGhhbiAxKSBvciBhIHJhZGlhbCBrZXJuZWwgd2lsbCBvdXRwZXJmb3JtIGEgc3VwcG9ydCB2ZWN0b3IgY2xhc3NpZmllciBvbiB0aGUgdHJhaW5pbmcgZGF0YS4gV2hpY2ggdGVjaG5pcXVlIHBlcmZvcm1zIGJlc3Qgb24gdGhlIHRlc3QgZGF0YT8gTWFrZSBwbG90cyBhbmQgcmVwb3J0IHRyYWluaW5nIGFuZCB0ZXN0IGVycm9yIHJhdGVzIGluIG9yZGVyIHRvIGJhY2sgdXAgeW91ciBhc3NlcnRpb25zLioKCkdlbmVyYXRlIGRhdGE6CmBgYHtyfQojIFByZWxpbXM6CnNldC5zZWVkKDEpCgojIERhdGE6CngxIDwtIHJub3JtKDEwMCkKeDIgPC0gNCAqIHgxXjIgKyAxICsgcm5vcm0oMTAwKQoKY2xhc3MgPC0gc2FtcGxlKDEwMCwgNTApCngyW2NsYXNzXSA8LSB4MltjbGFzc10gKyAzCngyWy1jbGFzc10gPC0geDJbLWNsYXNzXSAtIDMKCnkgPC0gcmVwKC0xLCAxMDApCnlbY2xhc3NdIDwtIDEKCmRhdCA8LSBkYXRhLmZyYW1lKHgxID0geDEsCiAgICAgICAgICAgICAgICAgIHgyID0geDIsCiAgICAgICAgICAgICAgICAgIHkgPSBhcy5mYWN0b3IoeSkpCgojIEVycm9yczoKZXJyb3JfdHJhaW4gPC0gYygpCmVycm9yX3Rlc3QgPC0gYygpCgojIFRyYWluL1Rlc3QKdHJhaW4gPC0gc2FtcGxlKDEwMCwgODApCnRlc3QgPSAtdHJhaW4KCiMgUGxvdHM6CmdncGxvdChkYXQpICsKICBnZW9tX3BvaW50KGFlcyh4MSwgeDIsIGdyb3VwID0geSwgY29sb3IgPSB5KSkgKwogIHRoZW1lX2J3KCkKYGBgCgojIyMgU3VwcG9ydCBWZWN0b3IgQ2xhc3NpZmllciAgCgpUcmFpbiBhIHN1cHBvcnQgdmVjdG9yIGNsYXNzaWZpZXIgKGxpbmVhciBrZXJuZWwpIG9uIGEgcmFuZ2Ugb2YgdmFsdWVzIGZvciBgY29zdGA6CmBgYHtyfQpzZXQuc2VlZCgxKQp0dW5lLm91dF80X3N2YyA8LSB0dW5lKHN2bSwgeSB+IC4sIGRhdGEgPSBkYXRbdHJhaW4sIF0sIGtlcm5lbCA9ICJsaW5lYXIiLCByYW5nZXMgPSBsaXN0KGNvc3QgPSBjICgwLjAwMSwgMC4wMSwgMC4xLCAxLCA1LCAxMCwgMTAwKSkpCnN1bW1hcnkodHVuZS5vdXRfNF9zdmMpCmBgYAoKRXh0cmFjdCB0aGUgYmVzdCBtb2RlbCBhbmQgcHJpbnQgc3VtbWFyeToKYGBge3J9CmJlc3Rtb2RfNF9zdmMgPC0gdHVuZS5vdXRfNF9zdmMkYmVzdC5tb2RlbApzdW1tYXJ5KGJlc3Rtb2RfNF9zdmMpCmBgYAoKUGxvdCB0aGUgZGVjaXNpb24gYm91bmRhcnk6CmBgYHtyfQojcGxvdChiZXN0bW9kXzRfc3ZjLCBkYXRbdHJhaW4sIF0pCnN2bV9wbG90KGJlc3Rtb2RfNF9zdmMsIGRhdFt0cmFpbiwgXSkKYGBgCgpUaGUgbGluZWFyIGNsYXNzaWZpZXIgZmFpbHMgdG8gYWNjdXJhdGVseSBjYXB0dXJlIHRoZSBub24tbGluZWFyaXR5IG9mIHRoZSBkZWNpc2lvbiBib3VuZGFyeS4KCiMjIyMgVHJhaW5pbmcgZXJyb3IKYGBge3J9Cm1lYW4oZGF0W3RyYWluLCAieSJdICE9IHByZWRpY3QoYmVzdG1vZF80X3N2YywgbmV3ZGF0YSA9IGRhdFt0cmFpbiwgXSkpCnN2Y19lcnJvcl90cmFpbiA8LSBtZWFuKHN1bW1hcnkoYmVzdG1vZF80X3N2YykkZml0dGVkICE9IHlbdHJhaW5dKQplcnJvcl90cmFpbiA8LSBjKGVycm9yX3RyYWluLCAic3ZjIiA9IHN2Y19lcnJvcl90cmFpbikKc3ZjX2Vycm9yX3RyYWluCmBgYAoKIyMjIyBUZXN0IEVycm9yCgpgYGB7cn0KeXByZWQgPC0gcHJlZGljdChiZXN0bW9kXzRfc3ZjLCBkYXRbdGVzdCwgXSkKdGFibGUocHJlZGljdCA9IHlwcmVkLCB0cnV0aCA9IHlbdGVzdF0pCmBgYAoKYGBge3J9CnN2Y19lcnJvcl90ZXN0IDwtIG1lYW4oeXByZWQgIT0geVt0ZXN0XSkKZXJyb3JfdGVzdCA8LSBjKGVycm9yX3Rlc3QsICJzdmMiID0gc3ZjX2Vycm9yX3Rlc3QpCnN2Y19lcnJvcl90ZXN0CmBgYAoKIyMjIFN1cHBvcnQgVmVjdG9yIE1hY2hpbmUgLSBQb2x5bm9taWFsIEtlcm5lbCAoJGQkID0gMikKClRyYWluIGEgc3VwcG9ydCB2ZWN0b3IgbWFjaGluZSAocG9seW5vbWlhbCBrZXJuZWwsICRkJCA9IDIpIG9uIGEgcmFuZ2Ugb2YgdmFsdWVzIGZvciBgY29zdGA6CmBgYHtyfQpzZXQuc2VlZCgxKQp0dW5lLm91dF80X3N2bSA8LSB0dW5lKHN2bSwgeSB+IC4sIGRhdGEgPSBkYXRbdHJhaW4sIF0sIGtlcm5lbCA9ICJwb2x5bm9taWFsIiwgZGVncmVlID0gMiwgcmFuZ2VzID0gbGlzdChjb3N0ID0gYyAoMC4wMDEsIDAuMDEsIDAuMSwgMSwgNSwgMTAsIDEwMCkpKQpzdW1tYXJ5KHR1bmUub3V0XzRfc3ZtKQpgYGAKCkV4dHJhY3QgdGhlIGJlc3QgbW9kZWwgYW5kIHByaW50IHN1bW1hcnk6CmBgYHtyfQpiZXN0bW9kXzRfc3ZtIDwtIHR1bmUub3V0XzRfc3ZtJGJlc3QubW9kZWwKc3VtbWFyeShiZXN0bW9kXzRfc3ZtKQpgYGAKClBsb3QgdGhlIGRlY2lzaW9uIGJvdW5kYXJ5OgpgYGB7cn0KI3Bsb3QoYmVzdG1vZF80X3N2bSwgZGF0W3RyYWluLCBdKQpzdm1fcGxvdChiZXN0bW9kXzRfc3ZtLCBkYXRbdHJhaW4sIF0pCmBgYAoKVGhlIGRlZ3JlZS0yIHBvbHlub21pYWwga2VybmVsIGNhcHR1cmVzIHNvbWUgb2YgdGhlIG5vbi1saW5lYXJpdHkgb2YgdGhlIGRlY2lzaW9uIGJvdW5kYXJ5LCBidXQgdGhlcmUgYXJlIG1hbnkgZXJyb3JzLgoKIyMjIyBUcmFpbmluZyBlcnJvcgpgYGB7cn0KI21lYW4oZGF0W3RyYWluLCAieSJdICE9IHByZWRpY3QoYmVzdG1vZF80X3N2bSwgbmV3ZGF0YSA9IGRhdFt0cmFpbiwgXSkpCnN2bV9lcnJvcl90cmFpbiA8LSBtZWFuKHN1bW1hcnkoYmVzdG1vZF80X3N2bSkkZml0dGVkICE9IHlbdHJhaW5dKQplcnJvcl90cmFpbiA8LSBjKGVycm9yX3RyYWluLCAic3ZtIChkID0gMikiID0gc3ZtX2Vycm9yX3RyYWluKQpzdm1fZXJyb3JfdHJhaW4KYGBgCgojIyMjIFRlc3QgRXJyb3IKCmBgYHtyfQp5cHJlZCA8LSBwcmVkaWN0KGJlc3Rtb2RfNF9zdm0sIGRhdFt0ZXN0LCBdKQp0YWJsZShwcmVkaWN0ID0geXByZWQsIHRydXRoID0gZGF0W3Rlc3QsICJ5Il0pCmBgYAoKYGBge3J9CnN2bV9lcnJvcl90ZXN0IDwtIG1lYW4oeXByZWQgIT0geVt0ZXN0XSkKZXJyb3JfdGVzdCA8LSBjKGVycm9yX3Rlc3QsICJzdm0gKGQgPSAyKSIgPSBzdm1fZXJyb3JfdGVzdCkKc3ZtX2Vycm9yX3Rlc3QKYGBgCgojIyMgU3VwcG9ydCBWZWN0b3IgTWFjaGluZSAtIFBvbHlub21pYWwgS2VybmVsICgkZCQgPSAzKQoKVHJhaW4gYSBzdXBwb3J0IHZlY3RvciBtYWNoaW5lIChwb2x5bm9taWFsIGtlcm5lbCwgJGQkID0gMykgb24gYSByYW5nZSBvZiB2YWx1ZXMgZm9yIGBjb3N0YDoKYGBge3J9CnNldC5zZWVkKDEpCnR1bmUub3V0XzRfc3ZtXzIgPC0gdHVuZShzdm0sIHkgfiAuLCBkYXRhID0gZGF0W3RyYWluLCBdLCBrZXJuZWwgPSAicG9seW5vbWlhbCIsIGRlZ3JlZSA9IDMsIHJhbmdlcyA9IGxpc3QoY29zdCA9IGMgKDAuMDAxLCAwLjAxLCAwLjEsIDEsIDUsIDEwLCAxMDApKSkKc3VtbWFyeSh0dW5lLm91dF80X3N2bV8yKQpgYGAKCkV4dHJhY3QgdGhlIGJlc3QgbW9kZWwgYW5kIHByaW50IHN1bW1hcnk6CmBgYHtyfQpiZXN0bW9kXzRfc3ZtXzIgPC0gdHVuZS5vdXRfNF9zdm1fMiRiZXN0Lm1vZGVsCnN1bW1hcnkoYmVzdG1vZF80X3N2bV8yKQpgYGAKClBsb3QgdGhlIGRlY2lzaW9uIGJvdW5kYXJ5OgpgYGB7cn0KI3Bsb3QoYmVzdG1vZF80X3N2bV8yLCBkYXRbdHJhaW4sIF0pCnN2bV9wbG90KGJlc3Rtb2RfNF9zdm1fMiwgZGF0W3RyYWluLCBdKQpgYGAKClRoZSBkZWdyZWUtMyBwb2x5bm9taWFsIGtlcm5lbCBjYXB0dXJlcyBzb21lIG9mIHRoZSBub24tbGluZWFyaXR5IG9mIHRoZSBkZWNpc2lvbiBib3VuZGFyeSwgYnV0IHRoZXJlIG1hbnkgZXJyb3JzLiBJdCBzZWVtcyB0aGF0IGEgcG9seW5vbWlhbCBvZiBkZWdyZWUgMyBpcyB3b3JzZSB0aGFuIHRoYXQgb2YgZGVncmVlIDIuCgojIyMgVHJhaW5pbmcgZXJyb3IgIApgYGB7cn0KbWVhbihkYXRbdHJhaW4sICJ5Il0gIT0gcHJlZGljdChiZXN0bW9kXzRfc3ZtXzIsIG5ld2RhdGEgPSBkYXRbdHJhaW4sIF0pKQpzdm1fMl9lcnJvcl90cmFpbiA8LSBtZWFuKHN1bW1hcnkoYmVzdG1vZF80X3N2bV8yKSRmaXR0ZWQgIT0geVt0cmFpbl0pCmVycm9yX3RyYWluIDwtIGMoZXJyb3JfdHJhaW4sICJzdm0gKGQgPSAzKSIgPSBzdm1fMl9lcnJvcl90cmFpbikKc3ZtXzJfZXJyb3JfdHJhaW4KYGBgCgojIyMgVGVzdCBFcnJvciAgCgpgYGB7cn0KeXByZWQgPC0gcHJlZGljdChiZXN0bW9kXzRfc3ZtXzIsIGRhdFt0ZXN0LCBdKQp0YWJsZShwcmVkaWN0ID0geXByZWQsIHRydXRoID0gZGF0W3Rlc3QsICJ5Il0pCmBgYAoKYGBge3J9CnN2bV8yX2Vycm9yX3Rlc3QgPC0gbWVhbih5cHJlZCAhPSB5W3Rlc3RdKQplcnJvcl90ZXN0IDwtIGMoZXJyb3JfdGVzdCwgInN2bSAoZCA9IDMpIiA9IHN2bV8yX2Vycm9yX3Rlc3QpCnN2bV8yX2Vycm9yX3Rlc3QKYGBgCgojIyMgU3VwcG9ydCBWZWN0b3IgTWFjaGluZSAtIFJhZGlhbCBLZXJuZWwKClRyYWluIGEgc3VwcG9ydCB2ZWN0b3IgbWFjaGluZSB3aXRoIGEgcmFkaWFsIGtlcm5lbCBvbiBhIHJhbmdlIG9mIHZhbHVlcyBmb3IgYGNvc3RgIGFuZCBgZ2FtbWFgOgpgYGB7cn0Kc2V0LnNlZWQoMSkKdHVuZS5vdXRfNF9zdm1fcmFkIDwtIHR1bmUoc3ZtLCB5IH4gLiwgZGF0YSA9IGRhdFt0cmFpbiwgXSwga2VybmVsID0gInJhZGlhbCIsIHJhbmdlcyA9IGxpc3QoY29zdCA9IGMgKDAuMDAxLCAwLjAxLCAwLjEsIDEsIDUsIDEwLCAxMDApLCBnYW1tYSA9IGMoMC41LCAxLCAyLCAzLCA0KSkpCnN1bW1hcnkodHVuZS5vdXRfNF9zdm1fcmFkKQpgYGAKCkV4dHJhY3QgdGhlIGJlc3QgbW9kZWwgYW5kIHByaW50IHN1bW1hcnk6CmBgYHtyfQpiZXN0bW9kXzRfc3ZtX3JhZCA8LSB0dW5lLm91dF80X3N2bV9yYWQkYmVzdC5tb2RlbApzdW1tYXJ5KGJlc3Rtb2RfNF9zdm1fcmFkKQpgYGAKClBsb3QgdGhlIGRlY2lzaW9uIGJvdW5kYXJ5OgpgYGB7cn0KI3Bsb3QoYmVzdG1vZF80X3N2bV9yYWQsIGRhdFt0cmFpbiwgXSkKc3ZtX3Bsb3QoYmVzdG1vZF80X3N2bV9yYWQsIGRhdFt0cmFpbiwgXSkKYGBgCgpUaGUgcmFkaWFsIGtlcm5lbCBoYXMgdmVyeSBhY2N1cmF0ZWx5IGNhcHR1cmVkIHRoZSBkZWNpc2lvbiBib3VuZGFyeS4gSW4gZmFjdCB0aGVyZSBhcmUgbm8gZXJyb3JzLgoKIyMjIyBUcmFpbmluZyBlcnJvciAgCmBgYHtyfQojbWVhbihkYXRbdHJhaW4sICJ5Il0gIT0gcHJlZGljdChiZXN0bW9kXzRfc3ZtX3JhZCwgbmV3ZGF0YSA9IGRhdFt0cmFpbiwgXSkpCnN2bV9yYWRfZXJyb3JfdHJhaW4gPC0gbWVhbihzdW1tYXJ5KGJlc3Rtb2RfNF9zdm1fcmFkKSRmaXR0ZWQgIT0geVt0cmFpbl0pCmVycm9yX3RyYWluIDwtIGMoZXJyb3JfdHJhaW4sICJzdm0gKHJhZGlhbCkiID0gc3ZtX3JhZF9lcnJvcl90cmFpbikKc3ZtX3JhZF9lcnJvcl90cmFpbgpgYGAKCiMjIyMgVGVzdCBFcnJvciAgCgpgYGB7cn0KeXByZWQgPC0gcHJlZGljdChiZXN0bW9kXzRfc3ZtX3JhZCwgZGF0W3Rlc3QsIF0pCnRhYmxlKHByZWRpY3QgPSB5cHJlZCwgdHJ1dGggPSBkYXRbdGVzdCwgInkiXSkKYGBgCgpgYGB7cn0Kc3ZtX3JhZF9lcnJvcl90ZXN0IDwtIG1lYW4oeXByZWQgIT0geVt0ZXN0XSkKZXJyb3JfdGVzdCA8LSBjKGVycm9yX3Rlc3QsICJzdm0gKHJhZGlhbCkiID0gc3ZtX3JhZF9lcnJvcl90ZXN0KQpzdm1fcmFkX2Vycm9yX3Rlc3QKYGBgCgojIyMgU3VtbWFyeSBvZiBFcnJvcnMKCmBgYHtyfQpzb3J0KGVycm9yX3RyYWluKQpzb3J0KGVycm9yX3Rlc3QpCmBgYAoKVGhlIFNWTSB3aXRoIHJhZGlhbCBrZXJuZWwgaGFzIHRoZSBiZXN0IHRyYWluaW5nIGFuZCB0ZXN0IGVycm9ycy4gSG93ZXZlciwgdGhlIGxpbmVhciBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyIG91dHBlcmZvcm1lZCBib3RoIG9mIHRoZSBTVk0ncyB3aXRoIHBvbHlub21pYWwga2VybmVscy4KClJlZG8gdGhlIGFuYWx5c2lzIHdpdGggYSBtb3JlIGNvbXBsZXggbm9uLWxpbmVhciBkZWNpc2lvbiBib3VuZGFyeSB0byBzZWUgaWYgdGhlIHBvbHlub21pYWwga2VybmVscyBvdXRwZXJmb3JtIHRoZSBsaW5lYXIga2VybmVsOgpgYGB7cn0KIyBQcmVsaW1zOgpzZXQuc2VlZCgxKQoKIyBEYXRhOgp4MSA8LSBybm9ybSgxMDApCngyIDwtIDQgKiB4MV4yICsgMSArIHJub3JtKDEwMCkKCmNsYXNzIDwtIHNhbXBsZSgxMDAsIDUwKQp4MltjbGFzc1sxOjI1XV0gPC0geDJbY2xhc3NbMToyNV1dICsgMwp4MltjbGFzc1syNTo1MF1dIDwtIHgyW2NsYXNzWzI1OjUwXV0gLSAxMAp4MlstY2xhc3NdIDwtIHgyWy1jbGFzc10gLSAzCgp5IDwtIHJlcCgtMSwgMTAwKQp5W2NsYXNzXSA8LSAxCgpkYXQgPC0gZGF0YS5mcmFtZSh4MSA9IHgxLAogICAgICAgICAgICAgICAgICB4MiA9IHgyLAogICAgICAgICAgICAgICAgICB5ID0gYXMuZmFjdG9yKHkpKQoKIyBFcnJvcnM6CmVycm9yX3RyYWluIDwtIGMoKQplcnJvcl90ZXN0IDwtIGMoKQoKIyBUcmFpbi9UZXN0CnRyYWluIDwtIHNhbXBsZSgxMDAsIDgwKQp0ZXN0ID0gLXRyYWluCgojIFBsb3RzOgpnZ3Bsb3QoZGF0KSArCiAgZ2VvbV9wb2ludChhZXMoeDEsIHgyLCBncm91cCA9IHksIGNvbG9yID0geSkpICsKICB0aGVtZV9idygpCmBgYAoKIyMjIFN1cHBvcnQgVmVjdG9yIENsYXNzaWZpZXIgIApgYGB7cn0Kc2V0LnNlZWQoMSkKdHVuZS5vdXRfNF9zdmMgPC0gdHVuZShzdm0sIHkgfiAuLCBkYXRhID0gZGF0W3RyYWluLCBdLCBrZXJuZWwgPSAibGluZWFyIiwgcmFuZ2VzID0gbGlzdChjb3N0ID0gYyAoMC4wMDEsIDAuMDEsIDAuMSwgMSwgNSwgMTAsIDEwMCkpKQpiZXN0bW9kXzRfc3ZjIDwtIHR1bmUub3V0XzRfc3ZjJGJlc3QubW9kZWwKI3Bsb3QoYmVzdG1vZF80X3N2YywgZGF0W3RyYWluLCBdKQpzdm1fcGxvdChiZXN0bW9kXzRfc3ZjLCBkYXRbdHJhaW4sIF0pCmBgYAoKVGhlIGxpbmVhciBjbGFzc2lmaWVyIGZhaWxzIHRvIGNhcHR1cmUgYW55IG9mIHRoZSBub24tbGluZWFyIGRlY2lzaW9uIGJvdW5kYXJ5LgoKIyMjIyBUcmFpbmluZyBlcnJvciAgCmBgYHtyfQpzdmNfZXJyb3JfdHJhaW4gPC0gbWVhbihzdW1tYXJ5KGJlc3Rtb2RfNF9zdmMpJGZpdHRlZCAhPSB5W3RyYWluXSkKZXJyb3JfdHJhaW4gPC0gYyhlcnJvcl90cmFpbiwgInN2YyIgPSBzdmNfZXJyb3JfdHJhaW4pCmBgYAoKIyMjIyBUZXN0IEVycm9yICAKYGBge3J9CnlwcmVkIDwtIHByZWRpY3QoYmVzdG1vZF80X3N2YywgZGF0W3Rlc3QsIF0pCnRhYmxlKHByZWRpY3QgPSB5cHJlZCwgdHJ1dGggPSB5W3Rlc3RdKQpzdmNfZXJyb3JfdGVzdCA8LSBtZWFuKHlwcmVkICE9IHlbdGVzdF0pCmVycm9yX3Rlc3QgPC0gYyhlcnJvcl90ZXN0LCAic3ZjIiA9IHN2Y19lcnJvcl90ZXN0KQpgYGAKCgojIyMgU3VwcG9ydCBWZWN0b3IgTWFjaGluZSAtIFBvbHlub21pYWwgS2VybmVsICgkZCQgPSAyKQoKYGBge3J9CnNldC5zZWVkKDEpCnR1bmUub3V0XzRfc3ZtIDwtIHR1bmUoc3ZtLCB5IH4gLiwgZGF0YSA9IGRhdFt0cmFpbiwgXSwga2VybmVsID0gInBvbHlub21pYWwiLCBkZWdyZWUgPSAyLCByYW5nZXMgPSBsaXN0KGNvc3QgPSBjICgwLjAwMSwgMC4wMSwgMC4xLCAxLCA1LCAxMCwgMTAwKSkpCmJlc3Rtb2RfNF9zdm0gPC0gdHVuZS5vdXRfNF9zdm0kYmVzdC5tb2RlbAojcGxvdChiZXN0bW9kXzRfc3ZtLCBkYXRbdHJhaW4sIF0pCnN2bV9wbG90KGJlc3Rtb2RfNF9zdm0sIGRhdFt0cmFpbiwgXSkKYGBgCgpUaGUgZGVncmVlLTIgcG9seW5vbWlhbCBrZXJuZWwgY2FwdHVyZXMgc29tZSBvZiB0aGUgbm9uLWxpbmVhcml0eSBvZiB0aGUgZGVjaXNpb24gYm91bmRhcnksIGJ1dCB0aGVyZSBtYW55IGVycm9ycy4KCiMjIyMgVHJhaW5pbmcgZXJyb3IKYGBge3J9CiNtZWFuKGRhdFt0cmFpbiwgInkiXSAhPSBwcmVkaWN0KGJlc3Rtb2RfNF9zdm0sIG5ld2RhdGEgPSBkYXRbdHJhaW4sIF0pKQpzdm1fZXJyb3JfdHJhaW4gPC0gbWVhbihzdW1tYXJ5KGJlc3Rtb2RfNF9zdm0pJGZpdHRlZCAhPSB5W3RyYWluXSkKZXJyb3JfdHJhaW4gPC0gYyhlcnJvcl90cmFpbiwgInN2bSAoZCA9IDIpIiA9IHN2bV9lcnJvcl90cmFpbikKYGBgCgojIyMjIFRlc3QgRXJyb3IKCmBgYHtyfQp5cHJlZCA8LSBwcmVkaWN0KGJlc3Rtb2RfNF9zdm0sIGRhdFt0ZXN0LCBdKQp0YWJsZShwcmVkaWN0ID0geXByZWQsIHRydXRoID0gZGF0W3Rlc3QsICJ5Il0pCnN2bV9lcnJvcl90ZXN0IDwtIG1lYW4oeXByZWQgIT0geVt0ZXN0XSkKZXJyb3JfdGVzdCA8LSBjKGVycm9yX3Rlc3QsICJzdm0gKGQgPSAyKSIgPSBzdm1fZXJyb3JfdGVzdCkKYGBgCgojIyMgU3VwcG9ydCBWZWN0b3IgTWFjaGluZSAoUG9seW5vbWlhbCBLZXJuZWwsICRkJCA9IDMpCgpgYGB7cn0Kc2V0LnNlZWQoMSkKdHVuZS5vdXRfNF9zdm1fMiA8LSB0dW5lKHN2bSwgeSB+IC4sIGRhdGEgPSBkYXRbdHJhaW4sIF0sIGtlcm5lbCA9ICJwb2x5bm9taWFsIiwgZGVncmVlID0gMywgcmFuZ2VzID0gbGlzdChjb3N0ID0gYyAoMC4wMDEsIDAuMDEsIDAuMSwgMSwgNSwgMTAsIDEwMCkpKQpiZXN0bW9kXzRfc3ZtXzIgPC0gdHVuZS5vdXRfNF9zdm1fMiRiZXN0Lm1vZGVsCiNwbG90KGJlc3Rtb2RfNF9zdm1fMiwgZGF0W3RyYWluLCBdKQpzdm1fcGxvdChiZXN0bW9kXzRfc3ZtXzIsIGRhdFt0cmFpbiwgXSkKYGBgCgpUaGUgZGVncmVlLTMgcG9seW5vbWlhbCBrZXJuZWwgY2FwdHVyZXMgc29tZSBvZiB0aGUgbm9uLWxpbmVhcml0eSBvZiB0aGUgZGVjaXNpb24gYm91bmRhcnksIGJ1dCB0aGVyZSBtYW55IGVycm9ycy4KCiMjIyMgVHJhaW5pbmcgZXJyb3IgIApgYGB7cn0Kc3ZtXzJfZXJyb3JfdHJhaW4gPC0gbWVhbihzdW1tYXJ5KGJlc3Rtb2RfNF9zdm1fMikkZml0dGVkICE9IHlbdHJhaW5dKQplcnJvcl90cmFpbiA8LSBjKGVycm9yX3RyYWluLCAic3ZtIChkID0gMykiID0gc3ZtXzJfZXJyb3JfdHJhaW4pCmBgYAoKIyMjIyBUZXN0IEVycm9yICAKCmBgYHtyfQp5cHJlZCA8LSBwcmVkaWN0KGJlc3Rtb2RfNF9zdm1fMiwgZGF0W3Rlc3QsIF0pCnN2bV8yX2Vycm9yX3Rlc3QgPC0gbWVhbih5cHJlZCAhPSB5W3Rlc3RdKQplcnJvcl90ZXN0IDwtIGMoZXJyb3JfdGVzdCwgInN2bSAoZCA9IDMpIiA9IHN2bV8yX2Vycm9yX3Rlc3QpCmBgYAoKIyMjIFN1cHBvcnQgVmVjdG9yIE1hY2hpbmUgLSBSYWRpYWwgS2VybmVsICAKCmBgYHtyfQpzZXQuc2VlZCgxKQp0dW5lLm91dF80X3N2bV9yYWQgPC0gdHVuZShzdm0sIHkgfiAuLCBkYXRhID0gZGF0W3RyYWluLCBdLCBrZXJuZWwgPSAicmFkaWFsIiwgcmFuZ2VzID0gbGlzdChjb3N0ID0gYyAoMC4wMDEsIDAuMDEsIDAuMSwgMSwgNSwgMTAsIDEwMCksIGdhbW1hID0gYygwLjUsIDEsIDIsIDMsIDQpKSkKYmVzdG1vZF80X3N2bV9yYWQgPC0gdHVuZS5vdXRfNF9zdm1fcmFkJGJlc3QubW9kZWwKI3Bsb3QoYmVzdG1vZF80X3N2bV9yYWQsIGRhdFt0cmFpbiwgXSkKc3ZtX3Bsb3QoYmVzdG1vZF80X3N2bV9yYWQsIGRhdFt0cmFpbiwgXSkKYGBgCgojIyMjIFRyYWluaW5nIGVycm9yICAKYGBge3J9CnN2bV9yYWRfZXJyb3JfdHJhaW4gPC0gbWVhbihzdW1tYXJ5KGJlc3Rtb2RfNF9zdm1fcmFkKSRmaXR0ZWQgIT0geVt0cmFpbl0pCmVycm9yX3RyYWluIDwtIGMoZXJyb3JfdHJhaW4sICJzdm0gKHJhZGlhbCkiID0gc3ZtX3JhZF9lcnJvcl90cmFpbikKYGBgCgojIyMjIFRlc3QgRXJyb3IgIAoKYGBge3J9CnlwcmVkIDwtIHByZWRpY3QoYmVzdG1vZF80X3N2bV9yYWQsIGRhdFt0ZXN0LCBdKQp0YWJsZShwcmVkaWN0ID0geXByZWQsIHRydXRoID0gZGF0W3Rlc3QsICJ5Il0pCnN2bV9yYWRfZXJyb3JfdGVzdCA8LSBtZWFuKHlwcmVkICE9IHlbdGVzdF0pCmVycm9yX3Rlc3QgPC0gYyhlcnJvcl90ZXN0LCAic3ZtIChyYWRpYWwpIiA9IHN2bV9yYWRfZXJyb3JfdGVzdCkKYGBgCgojIyMgU3VtbWFyeSBvZiBFcnJvcnMgIAoKYGBge3J9CnNvcnQoZXJyb3JfdHJhaW4pCnNvcnQoZXJyb3JfdGVzdCkKYGBgCgpUaGUgU1ZNIHdpdGggcmFkaWFsIGtlcm5lbCBoYXMgdGhlIGJlc3QgdHJhaW5pbmcgYW5kIHRlc3QgZXJyb3JzLiBUaGlzIHRpbWUsIHdpdGggYSBtb3JlIGNvbXBsZXggZGVjaXNpb24gYm91bmRhcnksIGJvdGggb2YgdGhlIFNWTSdzIHdpdGggcG9seW5vbWlhbCBrZXJuZWxzIG91dHBlcmZvcm1lZCB0aGUgbGluZWFyIHN1cHBvcnQgdmVjdG9yIGNsYXNzaWZpZXIuCgoqICogKgoKIyMgRXhlcmNpc2UgNQoKIyMjICZuYnNwOyZuYnNwOyhhKSAgCgpHZW5lcmF0ZSBhIGRhdGEgc2V0IHdpdGggJG4gPSA1MDAkIGFuZCAkcCA9IDIkLCBzdWNoIHRoYXQgdGhlIG9ic2VydmF0aW9ucyBiZWxvbmcgdG8gdHdvIGNsYXNzZXMgd2l0aCBhIHF1YWRyYXRpYyBkZWNpc2lvbiBib3VuZGFyeSBiZXR3ZWVuIHRoZW06CmBgYHtyfQpzZXQuc2VlZCgxKQp4MSA8LSBydW5pZig1MDApIC0gMC41CngyIDwtIHJ1bmlmKDUwMCkgLSAwLjUKeSA8LSAxKigoeDFeMiAtIHgyXjIpID4gMCkKZGYgPC0gZGF0YS5mcmFtZSh4MSwgeDIsIHkgPSBhcy5mYWN0b3IoeSkpIApgYGAKCiMjIyAmbmJzcDsmbmJzcDsoYikgIAoKUGxvdCB0aGUgb2JzZXJ2YXRpb25zLCBjb2xvcmVkIGFjY29yZGluZyB0byB0aGVpciBjbGFzcyBsYWJlbHM6CmBgYHtyfQpnMCA8LSBnZ3Bsb3QoZGYpICsKICBnZW9tX3BvaW50KGFlcyh4MSwgeDIsIGdyb3VwID0geSwgY29sb3IgPSB5KSkgKwogIHRoZW1lX2J3KCkgKwogIGdndGl0bGUoIlRydWUgQ2xhc3MgTGFiZWxzIikgKwogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKSArCiAgc2NhbGVfY29sb3JfZGlzY3JldGUobmFtZSA9ICJUcnVlIENsYXNzIikKZzAKYGBgCgojIyMgJm5ic3A7Jm5ic3A7KGMpICAKCipVc2UgYWxsIG9mIHRoZSBkYXRhIGFzIHRoZSB0cmFpbmluZyBkYXRhKgoKRml0IGEgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCB0byB0aGUgZGF0YSwgdXNpbmcgJFhfMSQgYW5kICRYXzIkIGFzIHByZWRpY3RvcnM6CmBgYHtyfQpsb2dyZWcgPC0gZ2xtKHkgfiB4MSArIHgyLCBkYXRhID0gZGYsIGZhbWlseSA9ICJiaW5vbWlhbCIpIApwcm9icyA8LSBwcmVkaWN0KGxvZ3JlZywgbmV3ZGF0YSA9IGRmLCB0eXBlID0gInJlc3BvbnNlIikKcHJlZHMgPC0gcmVwKDAsIDUwMCkKcHJlZHNbcHJvYnMgPiAwLjVdIDwtIDEKYGBgCgojIyMgJm5ic3A7Jm5ic3A7KGQpICAKCkFwcGx5IHRoaXMgbW9kZWwgdG8gdGhlIHRyYWluaW5nIGRhdGEgaW4gb3JkZXIgdG8gb2J0YWluIGEgcHJlZGljdGVkIGNsYXNzIGxhYmVsIGZvciBlYWNoIHRyYWluaW5nIG9ic2VydmF0aW9uLiBQbG90IHRoZSBvYnNlcnZhdGlvbnMsIGNvbG9yZWQgYWNjb3JkaW5nIHRvIHRoZSBwcmVkaWN0ZWQgY2xhc3MgbGFiZWxzLiBUaGUgZGVjaXNpb24gYm91bmRhcnkgc2hvdWxkIGJlIGxpbmVhcjoKYGBge3IgZmlnLndpZHRoPTEwfQpkZiRsb2dyZWdfcHJlZHMgPC0gYXMuZmFjdG9yKHByZWRzKQpnMSA8LSBnZ3Bsb3QoZGYpICsKICBnZW9tX3BvaW50KGFlcyh4MSwgeDIsIGdyb3VwID0gbG9ncmVnX3ByZWRzLCBjb2xvciA9IGxvZ3JlZ19wcmVkcykpICsKICB0aGVtZV9idygpICsKICBzY2FsZV9jb2xvcl9kaXNjcmV0ZShuYW1lID0gIlByZWQuIENsYXNzIikgKyAKICBnZ3RpdGxlKCJMb2dpc3RpYyBSZWdyZXNzaW9uOiB5IH4geDEgKyB4MiIpICsKICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkKY293cGxvdDo6cGxvdF9ncmlkKGcwLCBnMSwgbnJvdyA9IDEpCmBgYAoKIyMjICZuYnNwOyZuYnNwOyhlKSAgCgpOb3cgZml0IGEgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCB0byB0aGUgZGF0YSB1c2luZyBub24tbGluZWFyIGZ1bmN0aW9ucyBvZiAkWF8xJCBhbmQgJFhfMiQgYXMgcHJlZGljdG9yczoKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KZm9ybXVsYXMgPC0gYygieSB+IEkoeDFeMikgKyBJKHgyXjIpIiwKICAgICAgICAgICAgICAieSB+IEkoeDFeMC41KSArIEkoeDJeMC41KSIsCiAgICAgICAgICAgICAgInkgfiB4MSArIHgyICsgSSh4MV4yKSArIEkoeDJeMikiLAogICAgICAgICAgICAgICJ5IH4geDEgKyB4MiArIEkoeDFeMC41KSArIEkoeDJeMC41KSIsCiAgICAgICAgICAgICAgInkgfiB4MSArIHgyICsgSSh4MV4yKSArIEkoeDJeMikgKyBJKHgxICogeDIpIiwKICAgICAgICAgICAgICAieSB+IHgxICsgeDIgKyBJKHgxXjAuNSkgKyBJKHgyXjAuNSkgKyBJKHgxICogeDIpIgopCgpsb2dyZWdzIDwtIG1hcChmb3JtdWxhcywgfmdsbShhcy5mb3JtdWxhKC54KSwgZGF0YSA9IGRmLCBmYW1pbHkgPSAiYmlub21pYWwiKSkKcHJvYnMgPC0gbWFwKGxvZ3JlZ3MsIH5wcmVkaWN0KC54LCBuZXdkYXRhID0gZGYsIHR5cGUgPSAicmVzcG9uc2UiKSkKcHJlZHMgPC0gdmVjdG9yKCJsaXN0IiwgbGVuZ3RoKGZvcm11bGFzKSkKcHJlZHMgPC0gbWFwKDE6bGVuZ3RoKGZvcm11bGFzKSwgZnVuY3Rpb24oeCkgcHJlZHNbW3hdXSA9IHJlcCgwLCA1MDApKQpmb3IoaSBpbiAxOmxlbmd0aChmb3JtdWxhcykpIHsKICBwcmVkc1tbaV1dW3Byb2JzW1tpXV0gPiAwLjVdIDwtIDEKfQpgYGAKCiMjIyAmbmJzcDsmbmJzcDsoZikgICAKCldpdGggdGhlIG1vZGVscyBpbnZvbHZpbmcgdGhlIHNxdWFyZXMgb2YgdGhlIHByZWRpY3RvcnMgdGhlIHByZWRpY3RlZCByZXN1bHRzIGxvb2sgcXVpdGUgY2xvc2UgdG8gdGhlIHRydWUgdmFsdWVzLiBUaGUgbW9kZWxzIGludm9sdmluZyB0aGUgc3F1YXJlIHJvb3RzIGRvIG5vdCBwcmVkaWN0IHRoZSBjbGFzc2VzIHdlbGw6CmBgYHtyIGZpZy5oZWlnaHQ9MTIsIGZpZy53aWR0aD0xMH0KRzIgPC0gdmVjdG9yKCJsaXN0IiwgbGVuZ3RoKGZvcm11bGFzKSkKZm9yKGkgaW4gMTpsZW5ndGgoZm9ybXVsYXMpKSB7CiAgZGZfIDwtIGRhdGEuZnJhbWUoeDEsIHgyLCBwcmVkcyA9IGFzLmZhY3RvcihwcmVkc1tbaV1dKSkKICBHMltbaV1dIDwtIGdncGxvdChkZl8pICsKICAgICAgICAgICAgICAgICAgZ2VvbV9wb2ludChhZXMoeDEsIHgyLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBncm91cCA9IHByZWRzLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb2xvciA9IHByZWRzKSkgKwogICAgICAgICAgICAgICAgICBnZ3RpdGxlKGxhYmVsID0gcGFzdGUwKGZvcm11bGFzW2ldKSkgKwogICAgICAgICAgICAgICAgICB0aGVtZV9idygpICsKICAgICAgICAgICAgICAgICAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpICsKICAgIHNjYWxlX2NvbG9yX2Rpc2NyZXRlKG5hbWUgPSAiUHJlZC4gQ2xhc3MiKQp9Cgpjb3dwbG90OjpwbG90X2dyaWQocGxvdGxpc3QgPSBHMiwgbnJvdyA9IDMpCmBgYAoKIyMjICZuYnNwOyZuYnNwOyhnKSAgCgpGaXQgYSBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyIHRvIHRoZSBkYXRhIHdpdGggJFhfMSQgYW5kICRYXzIkIGFzIHByZWRpY3RvcnM6CmBgYHtyIGZpZy53aWR0aD0xMH0Kc3ZjLm91dCA8LSB0dW5lKHN2bSwgeSB+IC4sIGRhdGEgPSBkZiwga2VybmVsID0gImxpbmVhciIsIHJhbmdlcyA9IGxpc3QoY29zdCA9IGMgKDAuMDAxLCAwLjAxLCAwLjEsIDEsIDUsIDEwLCAxMDApKSkKc3ZjIDwtIHN2Yy5vdXQkYmVzdC5tb2RlbApwcmVkcyA8LSBwcmVkaWN0KHN2YywgZGYpCmRmXyA8LSBkYXRhLmZyYW1lKHgxLCB4MiwgcHJlZHMgPSBhcy5mYWN0b3IocHJlZHMpKQpnMyA8LSBnZ3Bsb3QoZGZfKSArCiAgZ2VvbV9wb2ludChhZXMoeDEsIHgyLAogICAgICAgICAgICAgZ3JvdXAgPSBwcmVkcywKICAgICAgICAgICAgIGNvbG9yID0gcHJlZHMpKSArCiAgICAgIGdndGl0bGUoIlN1cHBvcnQgVmVjdG9yIENsYXNzaWZpZXIiKSArCiAgICAgIHRoZW1lX2J3KCkgKwogICAgICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkgKwogICAgICBzY2FsZV9jb2xvcl9kaXNjcmV0ZShuYW1lID0gIlByZWQuIENsYXNzIikKY293cGxvdDo6cGxvdF9ncmlkKGcwLCBnMywgbnJvdyA9IDEpCmBgYAoKIyMjICZuYnNwOyZuYnNwOyhoKSAgCgpGaXQgYSBTVk0gdXNpbmcgYSBub24tbGluZWFyIGtlcm5lbCB0byB0aGUgZGF0YS4KCiMjIyMgU3VwcG9ydCB2ZWN0b3IgbWFjaGluZSB3aXRoIHBvbHlub21pYWwga2VybmVsLCAkZCQgPSAyICAKYGBge3IgZmlnLndpZHRoPTEwfQpzdm0ub3V0IDwtIHR1bmUoc3ZtLCB5IH4gLiwgZGF0YSA9IGRmLCBrZXJuZWwgPSAicG9seW5vbWlhbCIsIGRlZ3JlZSA9IDIsIHJhbmdlcyA9IGxpc3QoY29zdCA9IGMgKDAuMDAxLCAwLjAxLCAwLjEsIDEsIDUsIDEwLCAxMDApKSkKc3ZtMSA8LSBzdm0ub3V0JGJlc3QubW9kZWwKcHJlZHMgPC0gcHJlZGljdChzdm0xLCBkZikKZGZfIDwtIGRhdGEuZnJhbWUoeDEsIHgyLCBwcmVkcyA9IGFzLmZhY3RvcihwcmVkcykpCmc0IDwtIGdncGxvdChkZl8pICsKICBnZW9tX3BvaW50KGFlcyh4MSwgeDIsCiAgICAgICAgICAgICBncm91cCA9IHByZWRzLAogICAgICAgICAgICAgY29sb3IgPSBwcmVkcykpICsKICAgICAgZ2d0aXRsZSgiU3VwcG9ydCBWZWN0b3IgTWFjaGluZSAtIFBvbHlub21pYWwgS2VybmVsIChkID0gMikiKSArCiAgICAgIHRoZW1lX2J3KCkgKwogICAgICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41LCBzaXplID0gMTApKSArCiAgICAgIHNjYWxlX2NvbG9yX2Rpc2NyZXRlKG5hbWUgPSAiUHJlZC4gQ2xhc3MiKQpjb3dwbG90OjpwbG90X2dyaWQoZzAsIGc0LCBucm93ID0gMSkKYGBgCgojIyMjIFN1cHBvcnQgdmVjdG9yIG1hY2hpbmUgd2l0aCByYWRpYWwga2VybmVsCgpgYGB7ciBmaWcud2lkdGg9MTB9CnN2bS5vdXQyIDwtIHR1bmUoc3ZtLCB5IH4gLiwgZGF0YSA9IGRmLCBrZXJuZWwgPSAicmFkaWFsIiwgZGVncmVlID0gMiwgcmFuZ2VzID0gbGlzdChjb3N0ID0gYyAoMC4wMDEsIDAuMDEsIDAuMSwgMSwgNSwgMTAsIDEwMCksIGdhbW1hID0gYygwLjUsIDEsIDIsIDMsIDQpKSkKc3ZtX3JhZCA8LSBzdm0ub3V0JGJlc3QubW9kZWwKcHJlZHMgPC0gcHJlZGljdChzdm1fcmFkLCBkZikKZGZfIDwtIGRhdGEuZnJhbWUoeDEsIHgyLCBwcmVkcyA9IGFzLmZhY3RvcihwcmVkcykpCmc1IDwtIGdncGxvdChkZl8pICsKICBnZW9tX3BvaW50KGFlcyh4MSwgeDIsCiAgICAgICAgICAgICBncm91cCA9IHByZWRzLAogICAgICAgICAgICAgY29sb3IgPSBwcmVkcykpICsKICAgICAgZ2d0aXRsZSgiU3VwcG9ydCBWZWN0b3IgTWFjaGluZSAtIFJhZGlhbCBLZXJuZWwiKSArCiAgICAgIHRoZW1lX2J3KCkgKwogICAgICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41LCBzaXplID0gMTIpKSArCiAgICAgIHNjYWxlX2NvbG9yX2Rpc2NyZXRlKG5hbWUgPSAiUHJlZC4gQ2xhc3MiKQpjb3dwbG90OjpwbG90X2dyaWQoZzAsIGc1LCBucm93ID0gMSkKYGBgCgojIyMgJm5ic3A7Jm5ic3A7KGkpICAKClRoZSBsb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVsIHdpdGggbGluZWFyIGNvbWJpbmF0aW9uIG9mIHRoZSB2YXJpYWJsZXMgYW5kIHRoZSBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyIGJvdGggcGVyZm9ybWVkIHBvb3JseS4gVGhlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwgd2l0aCBub24tbGluZWFyIHRyYW5zZm9ybWF0aW9ucyBvZiB0aGUgdmFyaWFibGVzLCBhcyB3ZWxsIGFzIHN1cHBvcnQgdmVjdG9yIG1hY2hpbmVzIHdpdGggcG9seW5vbWlhbCBhbmQgcmFkaWFsIGtlcm5lbHMgYWxsIHBlcmZvcm1lZCB3ZWxsLiAKCmBgYHtyIGZpZy5oZWlnaHQ9MTIsIGZpZy53aWR0aD0xMH0KZzIgPC0gRzJbWzFdXSArIGdndGl0bGUoIkxvZ2lzdGljIFJlZ3Jlc3Npb246IHkgfiBJKHgxXjIpICsgSSh4Ml4yKSIpCmNvd3Bsb3Q6OnBsb3RfZ3JpZChnMCwgZzEsIGcyLCBnMywgZzQsIGc1LCBucm93ID0gMykKYGBgCgoqICogKgoKIyMgRXhlcmNpc2UgNgoKSXQncyBoYXJkIHRvIGZpZ3VyZSBvdXQgZXhhY3RseSB3aGF0IHRoZSBiZXN0IHR5cGUgb2YgZGF0YSBpcyBmb3IgdGhpcyBxdWVzdGlvbi4gTW9zdCBvZiB0aGUgZGF0YSBzZXRzIHRyaWVkIHJlc3VsdCBpbiB6ZXJvIHRlc3QgZXJyb3IgYXMgdGhlIGNvc3QgaW5jcmVhc2VzLiBVc2luZyB0aGUgYmVsb3cgZGF0YSBzZXQgd2l0aCBhIG1vZGVzdCAkbiQgb2YgMTAwIHNlZW1zIHRvIHdvcmsgZm9yIHdoYXQgdGhlIHF1ZXN0aW9uIGFza3MsIGkuZS4gdGhlIHRlc3QgZXJyb3IgZ2V0cyB0byBhIG1pbmltdW0gYmVmb3JlIHJpc2luZyBhZ2FpbiBhcyB0aGUgY29zdCBpbmNyZWFzZXMuCgojIyMgJm5ic3A7Jm5ic3A7KGEpICAKYGBge3J9CiMgUHJlbGltOgpzZXQuc2VlZCgxKQoKIyBEYXRhOgpuIDwtIDEwMAp4MSA8LSBydW5pZihuLCBtYXggPSAwLjMsIG1pbiA9IC0wLjMpCngyIDwtIHJub3JtKG4sIHNkID0gMSkKeSA8LSBpZmVsc2UoLTAuMiAqIHgxICsgeDIgPiAwLCAxLCAtMSkKZGYgPC0gZGF0YS5mcmFtZSh4MSwgeDIsIHkgPSBhcy5mYWN0b3IoeSkpCgojIFRyYWluL1Rlc3Q6CnRyYWluIDwtIHNhbXBsZShuLCA0Km4vNSkKdGVzdCA8LSAtdHJhaW4KCiMgUGxvdDoKZ2dwbG90KGRmKSArCiAgZ2VvbV9wb2ludChhZXMoeDEsIHgyLCBncm91cCA9IHksIGNvbG9yID0geSkpICsKICB0aGVtZV9idygpICsKICBnZ3RpdGxlKCJUcnVlIENsYXNzIExhYmVscyIpICsKICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkgKwogIHNjYWxlX2NvbG9yX2Rpc2NyZXRlKG5hbWUgPSAiVHJ1ZSBDbGFzcyIsIGJyZWFrcyA9IGMoMSwgLTEpKQpgYGAKCiMjIyAmbmJzcDsmbmJzcDsoYikgYW5kIChjKQoKR2VuZXJhdGUgc3VwcG9ydCB2ZWN0b3IgY2xhc3NpZmllcnMgdmlhIGNyb3NzIHZhbGlkYXRpb24gdXNpbmcgYSByYW5nZSBvZiB2YWx1ZXMgZm9yIGBjb3N0YCAodXNlIGFsbCBvZiB0aGUgZGF0YSBmb3IgQ1YsIHRoZW4gd2Ugd2lsbCB1c2UgdGhlIHRyYWluaW5nL3Rlc3Qgc3BsaXRzIGluIHRoZSBuZXh0IHNlY3Rpb24pOgpgYGB7cn0KY29zdHMgPC0gYyAoMC4wMDEsIDAuMDEsIDAuMSwgMSwgNSwgMTAsIDEwMCwgMWUzLCAxZTQsIDFlNSkKc3ZjLm91dCA8LSB0dW5lKHN2bSwgeSB+IC4sIGRhdGEgPSBkZiwga2VybmVsID0gImxpbmVhciIsIHJhbmdlcyA9IGxpc3QoY29zdCA9IGNvc3RzKSkKc3ZjLmN2LmVycm9yIDwtIHN2Yy5vdXQkcGVyZm9ybWFuY2VzJGVycm9yICMgZXh0cmFjdCB0aGUgQ1YgZXJyb3JzCnN2Yy5jdi5lcnJvcgpgYGAKClRoZSB0cmFpbmluZyBhbmQgdGVzdCBlcnJvcnMgY2FuIGJlIG9idGFpbmVkIGJ5IHRyYWluaW5nIFNWQyBtb2RlbHMgdXNpbmcgYSByYW5nZSBvZiB2YWx1ZXMgZm9yIGBjb3N0YCBhbmQgdGhlbiBtYWtpbmcgcHJlZGljdGlvbnMgb24gdGhlIHRyYWluaW5nIGFuZCB0ZXN0IGRhdGEgcmVzcGVjdGl2ZWx5OgpgYGB7cn0Kc3ZjLnRyYWluLmVycm9yIDwtIHZlY3RvcigiZG91YmxlIiwgbGVuZ3RoKGNvc3RzKSkKc3ZjLnRlc3QuZXJyb3IgPC0gdmVjdG9yKCJkb3VibGUiLCBsZW5ndGgoY29zdHMpKQpHIDwtIHZlY3RvcigibGlzdCIsIGxlbmd0aChjb3N0cykpCmZvcihpIGluIDE6bGVuZ3RoKGNvc3RzKSkgewogIHN2YyA8LSBzdm0oeSB+IC4sIGRhdGEgPSBkZlt0cmFpbiwgXSwga2VybmVsID0gImxpbmVhciIsIGNvc3QgPSBjb3N0c1tpXSkKICBHW1tpXV0gPC0gc3ZtX3Bsb3Qoc3ZjLCBkZlt0cmFpbiwgXSkgKyBnZ3RpdGxlKHN0cl9jKCJjb3N0OiAiLCBjb3N0c1tpXSkpCiAgCiAgIyBUcmFpbmluZyBFcnJvcjoKICBwcmVkcyA8LSBwcmVkaWN0KHN2YywgZGZbdHJhaW4sIF0pCiAgdHJhaW4uZXJyb3IgPC0gbWVhbihwcmVkcyAhPSB5W3RyYWluXSkKICBzdmMudHJhaW4uZXJyb3JbaV0gPC0gdHJhaW4uZXJyb3IKICAKICAjIFRlc3QgRXJyb3I6CiAgcHJlZHMgPC0gcHJlZGljdChzdmMsIGRmW3Rlc3QsIF0pCiAgdGVzdC5lcnJvciA8LSBtZWFuKHByZWRzICE9IHlbdGVzdF0pCiAgc3ZjLnRlc3QuZXJyb3JbaV0gPC0gdGVzdC5lcnJvcgp9CgpzdmMudHJhaW4uZXJyb3IKc3ZjLnRlc3QuZXJyb3IKYGBgCgpgYGB7ciBmaWcuaGVpZ2h0PTEyLCBmaWcud2lkdGg9MTB9CnBsb3RfZ3JpZChwbG90bGlzdCA9IEcsIG5yb3cgPSA1KQpgYGAKClBsb3QgdGhlIENWLCB0cmFpbmluZywgYW5kIHRlc3QgZXJyb3JzOgpgYGB7cn0KbGlicmFyeShsYXRleDJleHApCnN2Yy5lcnJvcnMgPC0gZGF0YS5mcmFtZShjb3N0ID0gbG9nMTAoY29zdHMpLAogICAgICAgICAgICAgICAgICAgICAgICAgY3YuZXJyb3IgPSBzdmMuY3YuZXJyb3IsCiAgICAgICAgICAgICAgICAgICAgICAgICB0cmFpbi5lcnJvciA9IHN2Yy50cmFpbi5lcnJvciwKICAgICAgICAgICAgICAgICAgICAgICAgIHRlc3QuZXJyb3IgPSBzdmMudGVzdC5lcnJvcikKCiMgc2VlIGh0dHBzOi8vc3RhY2tvdmVyZmxvdy5jb20vYS81MDQ5Njg5OSBhbmQgaHR0cHM6Ly9zdGFja292ZXJmbG93LmNvbS9hLzEwMzU1ODQ0IGZvciBtYWtpbmcgbGVnZW5kCmdncGxvdChzdmMuZXJyb3JzKSArCiAgZ2VvbV9saW5lKGFlcyhjb3N0LCBjdi5lcnJvciwgY29sb3IgPSAiQ1YiKSkgKwogIGdlb21fbGluZShhZXMoY29zdCwgdHJhaW4uZXJyb3IsIGNvbG9yID0gIlRyYWluIikpICsKICBnZW9tX2xpbmUoYWVzKGNvc3QsIHRlc3QuZXJyb3IsIGNvbG9yID0gIlRlc3QiKSkgKwogIGdlb21faGxpbmUoYWVzKHlpbnRlcmNlcHQgPSBtaW4oc3ZjLnRlc3QuZXJyb3IpKSwgY29sb3IgPSAiZ3JleTMwIiwgbGluZXR5cGUgPSAiZGFzaGVkIikgKwogIHNjYWxlX2NvbG9yX21hbnVhbChuYW1lID0gIkVycm9yIFJhdGUiLCBicmVha3MgPSBjKCJUZXN0IiwgIlRyYWluIiwgIkNWIiksIHZhbHVlcyA9IGMoIlRlc3QiID0gIiMwMEJBMzgiLCAiQ1YiID0gIiNGODc2NkQiLCAiVHJhaW4iID0gIiM2MTlDRkYiKSkgKwogICNzY2FsZV9jb2xvcl9kaXNjcmV0ZShuYW1lID0gTlVMTCwgbGFiZWxzID0gYygiQ1YgRXJyb3IiLCAiVGVzdCBFcnJvciIsICJUcmFpbmluZyBFcnJvciIpKSArCiAgbGFicyh0aXRsZSA9ICJDb21wYXJpc29uIG9mIENWLCBUcmFpbmluZyBhbmQgVGVzdCBFcnJvciBSYXRlcyIsCiAgICAgICB4ID0gVGVYKCJMb2dfezEwfShDb3N0KSIpLAogICAgICAgeSA9ICJFcnJvciBSYXRlIikgKwogIHRoZW1lX2J3KCkgKwogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpLAogICAgICAgIGxlZ2VuZC5wb3NpdGlvbiA9IGMoMC45NywgMC45NSksIGxlZ2VuZC5qdXN0aWZpY2F0aW9uID0gYygxLCAxKSkKYGBgCgojIyMgJm5ic3A7Jm5ic3A7KGQpICAKClRoZSBlcnJvciByYXRlcyBhcHByb2FjaCB6ZXJvIGFzIHRoZSBjb3N0IGluY3JlYXNlcyBmcm9tIHNtYWxsIHZhbHVlcyB0b3dhcmRzIDEuIFRoZW4sIHRoZSB0ZXN0IGVycm9yIHN0YXJ0cyB0byByaXNlIGFnYWluLCBzdWdnZXN0aW5nIHRoYXQgYSBsb3dlciB2YWx1ZSBmb3IgY29zdCBpcyBiZXR0ZXIsIGV2ZW4gdGhvdWdoIHRoZSB0cmFpbmluZyBlcnJvciBpcyB6ZXJvIGZvciBsYXJnZXIgdmFsdWVzLgoKKiAqICoKCiMjIEV4ZXJjaXNlIDcKClZpZXcgZGF0YToKYGBge3J9CkF1dG8KYGBgCgpTdW1tYXJ5OgpgYGB7cn0Kc3VtbWFyeShBdXRvKQpgYGAKCmBgYHtyfQpBdXRvJG9yaWdpbiA8LSBhcy5mYWN0b3IoQXV0byRvcmlnaW4pCkF1dG8keWVhciA8LSBmYWN0b3IoQXV0byR5ZWFyLCBvcmRlcmVkID0gVFJVRSkKYGBgCgpgYGB7cn0KaGVhZChBdXRvKQpgYGAKCiMjIyAmbmJzcDsmbmJzcDsoYSkgIAoKQ3JlYXRlIGEgYmluYXJ5IHZhcmlhYmxlIHRoYXQgdGFrZXMgb24gYSAxIGZvciBjYXJzIHdpdGggZ2FzIG1pbGVhZ2UgYWJvdmUgdGhlIG1lZGlhbiwgYW5kIGEgMCBmb3IgY2FycyB3aXRoIGdhcyBtaWxlYWdlIGJlbG93IHRoZSBtZWRpYW46CmBgYHtyfQpBdXRvJG1lZDAxIDwtIGFzLmZhY3RvcihBdXRvJG1wZyA+IG1lZGlhbihBdXRvJG1wZykpCkF1dG8gPC0gQXV0b1sgLCAtMV0Kc3VtbWFyeShBdXRvJG1lZDAxKQpgYGAKCiMjIyAmbmJzcDsmbmJzcDsoYikgIAoKRml0IGEgc3VwcG9ydCB2ZWN0b3IgY2xhc3NpZmllciB0byB0aGUgZGF0YSB3aXRoIHZhcmlvdXMgdmFsdWVzIG9mIGBjb3N0YCwgaW4gb3JkZXIgdG8gcHJlZGljdCB3aGV0aGVyIGEgY2FyIGdldHMgaGlnaCBvciBsb3cgZ2FzIG1pbGVhZ2U6CmBgYHtyfQpzZXQuc2VlZCgxKQpjb3N0cyA8LSBjICgwLjAwMSwgMC4wMSwgMC4xLCAxLCA1LCAxMCwgNTAsIDEwMCwgMjUwLCA1MDAsIDFlMywgNWUzLCAxZTQsIDVlNCwgMWU1KQpzdmMub3V0IDwtIHR1bmUoc3ZtLCBtZWQwMSB+IC4sIGRhdGEgPSBBdXRvLCBrZXJuZWwgPSAibGluZWFyIiwgcmFuZ2VzID0gbGlzdChjb3N0ID0gY29zdHMpKQpzdmMuY3YuZXJyb3IgPC0gc3ZjLm91dCRwZXJmb3JtYW5jZXMkZXJyb3IgIyBleHRyYWN0IHRoZSBDViBlcnJvcnMKc3ZjLmN2LmVycm9yCmBgYAoKUGxvdCBDViBlcnJvcnM6CmBgYHtyfQpnZ3Bsb3QoZGF0YS5mcmFtZShjb3N0ID0gbG9nMTAoY29zdHMpLCBjdi5lcnJvciA9IHN2Yy5jdi5lcnJvcikpICsKICBnZW9tX2xpbmUoYWVzKGNvc3QsIGN2LmVycm9yKSwgY29sb3IgPSBJU0xSX29yYW5nZSkgKwogIGxhYnModGl0bGUgPSAiQ1YgRXJyb3IgUmF0ZSBhcyBGdW5jdGlvbiBvZiBDb3N0IiwKICAgICAgIHggPSBUZVgoIkxvZ197MTB9KENvc3QpIiksCiAgICAgICB5ID0gIkNWIEVycm9yIFJhdGUiKSArCiAgdGhlbWVfYncoKSArCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpCmBgYAoKIyMjICZuYnNwOyZuYnNwOyhjKSAgCgpOb3cgcmVwZWF0IChiKSwgdGhpcyB0aW1lIHVzaW5nIFNWTXMgd2l0aCByYWRpYWwgYW5kIHBvbHlub21pYWwgYmFzaXMga2VybmVscywgd2l0aCBkaWZmZXJlbnQgdmFsdWVzIG9mIGBnYW1tYWAgYW5kIGBkZWdyZWVgIGFuZCBgY29zdGAuCgojIyMjIFBvbHlub21pYWwgS2VybmVsCgpgYGB7cn0Kc2V0LnNlZWQoMSkKY29zdHMgPC0gYyAoMC4wMDEsIDAuMDEsIDAuMSwgMSwgNSwgMTAsIDUwLCAxMDAsIDI1MCwgNTAwLCAxZTMsIDVlMywgMWU0LCA1ZTQsIDFlNSkKZGVncmVlcyA8LSBjKDIsIDMsIDQsIDUpCnN2Yy5vdXQucG9seSA8LSB0dW5lKHN2bSwgbWVkMDEgfiAuLCBkYXRhID0gQXV0bywga2VybmVsID0gInBvbHlub21pYWwiLCByYW5nZXMgPSBsaXN0KGRlZ3JlZSA9IGRlZ3JlZXMsIGNvc3QgPSBjb3N0cykpICMgZmlyc3QgdmFyaWFibGUgaW4gcmFuZ2VzIGlzIHRoZSByb3dzIGluIGJlbG93IG1hdHJpeApzdmMucG9seS5jdi5lcnJvciA8LSBzdmMub3V0LnBvbHkkcGVyZm9ybWFuY2VzJGVycm9yICMgZXh0cmFjdCB0aGUgQ1YgZXJyb3JzCnJvdW5kKG1hdHJpeChzdmMucG9seS5jdi5lcnJvciwgbnJvdyA9IGxlbmd0aChkZWdyZWVzKSksIDMpCmBgYAoKUGxvdCBDViBlcnJvcnM6CmBgYHtyIGZpZy5oZWlnaHQ9NCwgZmlnLndpZHRoPTh9CmRhdF8gPC0gZGF0YS5mcmFtZShjYmluZChjb3N0ID0gbG9nMTAoY29zdHMpLCB0KG1hdHJpeChzdmMucG9seS5jdi5lcnJvciwgbnJvdyA9IGxlbmd0aChkZWdyZWVzKSkpKSkgJT4lIAogICAgICAgIGdhdGhlcihrZXkgPSAiZGVncmVlIiwgdmFsdWUgPSAiY3YuZXJyb3IiLCBWMjpWNSkgJT4lIAogICAgICAgIG11dGF0ZShkZWdyZWUgPSBmYWN0b3Ioc3RyX3JlcGxhY2UoZGVncmVlLCAiViIsICJkZWdyZWU6ICIpKSkKCmdncGxvdChkYXRfKSArCiAgZ2VvbV9saW5lKGFlcyhjb3N0LCBjdi5lcnJvciwgY29sb3IgPSBkZWdyZWUpKSArCiAgbGFicyh0aXRsZSA9ICJQb2x5bm9taWFsIEtlcm5lbCAtIENWIEVycm9yIFJhdGUgYXMgRnVuY3Rpb24gb2YgQ29zdCIsCiAgICAgICB4ID0gVGVYKCJMb2dfezEwfShDb3N0KSIpLAogICAgICAgeSA9ICJDViBFcnJvciBSYXRlIikgKwogIGdnc2NpOjpzY2FsZV9jb2xvcl9kMygpICsKICB0aGVtZV9idygpICsKICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkKYGBgCgojIyMjIFJhZGlhbCBLZXJuZWwKCmBgYHtyfQpzZXQuc2VlZCgxKQpjb3N0cyA8LSBjKDAuMDAxLCAwLjAxLCAwLjEsIDEsIDUsIDEwLCA1MCwgMTAwLCAyNTAsIDUwMCwgMWUzLCA1ZTMsIDFlNCwgNWU0LCAxZTUpCmdhbW1hcyA9IGMoMC4wMSwgMC4wNSwgMC4xLCAwLjUpCnN2Yy5vdXQucmFkIDwtIHR1bmUoc3ZtLCBtZWQwMSB+IC4sIGRhdGEgPSBBdXRvLCBrZXJuZWwgPSAicG9seW5vbWlhbCIsIHJhbmdlcyA9IGxpc3QoZ2FtbWEgPSBnYW1tYXMsIGNvc3QgPSBjb3N0cykpICMgZmlyc3QgdmFyaWFibGUgaW4gcmFuZ2VzIGlzIHRoZSByb3dzIGluIGJlbG93IG1hdHJpeApzdmMucmFkLmN2LmVycm9yIDwtIHN2Yy5vdXQucmFkJHBlcmZvcm1hbmNlcyRlcnJvciAjIGV4dHJhY3QgdGhlIENWIGVycm9ycwpyb3VuZChtYXRyaXgoc3ZjLnJhZC5jdi5lcnJvciwgbnJvdyA9IGxlbmd0aChnYW1tYXMpKSwgMykKYGBgCgpQbG90IENWIGVycm9yczoKYGBge3IgZmlnLmhlaWdodD00LCBmaWcud2lkdGg9OH0KZGF0XyA8LSBkYXRhLmZyYW1lKGNiaW5kKGNvc3QgPSBsb2cxMChjb3N0cyksIHQobWF0cml4KHN2Yy5yYWQuY3YuZXJyb3IsIG5yb3cgPSBsZW5ndGgoZ2FtbWFzKSkpKSkgJT4lIAogICAgICAgIGdhdGhlcihrZXkgPSAiZ2FtbWEiLCB2YWx1ZSA9ICJjdi5lcnJvciIsIFYyOlY1KSAlPiUgCiAgICAgICAgbXV0YXRlKGdhbW1hID0gc3RyX2MoImdhbW1hOiAiLCBmYWN0b3IoZ2FtbWFzW2FzLm51bWVyaWMoc3RyX3JlbW92ZShnYW1tYSwgIlYiKSkgLSAxXSkpKSAjIGZhY3RvciB0byBtYWtlIGl0IGEgZGlzY3JldGUgdmFyIGluIGdncGxvdCgpCgpnZ3Bsb3QoZGF0XykgKwogIGdlb21fbGluZShhZXMoY29zdCwgY3YuZXJyb3IsIGNvbG9yID0gZ2FtbWEpKSArCiAgbGFicyh0aXRsZSA9ICJSYWRpYWwgS2VybmVsIC0gQ1YgRXJyb3IgUmF0ZSBhcyBGdW5jdGlvbiBvZiBDb3N0IiwKICAgICAgIHggPSBUZVgoIkxvZ197MTB9KENvc3QpIiksCiAgICAgICB5ID0gIkNWIEVycm9yIFJhdGUiKSArCiAgZ2dzY2k6OnNjYWxlX2NvbG9yX2QzKCkgKwogIHRoZW1lX2J3KCkgKwogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQpgYGAKCiMjIyAmbmJzcDsmbmJzcDsoZCkgIAoKQSBzdXBwb3J0IHZlY3RvciBtYWNoaW5lIHdpdGggYSBsaW5lYXIga2VybmVsIGFuZCBgY29zdCA9IDAuMWAgcGVyZm9ybXMgd2VsbCwgd2l0aCBhIENWIGVycm9yIG9mIDAuMDg3CgpBIHN1cHBvcnQgdmVjdG9yIG1hY2hpbmUgd2l0aCBhIHBvbHlub21pYWwga2VybmVsIG9mIGBkZWdyZWVgIHRocmVlIGFuZCBhbHNvIGFjaGlldmVzIGEgbG93IENWIGVycm9yIG9mIDAuMDguIEhvd2V2ZXIgdGhlIGBjb3N0YCBpcyB2ZXJ5IGxhcmdlIGF0IDEwMCwwMDAuCgpBIHN1cHBvcnQgdmVjdG9yIG1hY2hpbmUgd2l0aCBhIHJhZGlhbCBrZXJuZWwgYW5kIHBhcmFtZXRlcnMgb2YgYGNvc3QgPSAxYCBhbmQgYGdhbW1hID0gMC41YCBoYXMgdGhlIGxvd2VzdCBDViBlcnJvciBhdCAwLjA4OS4gT3RoZXIgcmFkaWFsIGtlcm5lbCBTVk0ncyB3aXRoIHZlcnkgbGFyZ2UgYGNvc3RgIHZhbHVlcyBhbHNvIGhhdmUgYW4gZXF1YWxseSBsb3cgQ1YgZXJyb3IsIGJ1dCBhIGBnYW1tYWAgdmFsdWUgb2YgMC41IHBlcmZvcm1zIHdlbGwgd2l0aCBsb3dlciBgY29zdGAgd2hpY2ggd291bGQgbGlrZWx5IG92ZXJmaXQgbGVzcyB0aGFuIHRoZSBvdGhlciBtb2RlbHMuCgoqICogKgoKIyMgRXhlcmNpc2UgOAoKVmlldyBkYXRhOgpgYGB7cn0KaGVhZChPSikKYGBgCgpTdW1tYXJ5OgpgYGB7cn0Kc3VtbWFyeShPSikKYGBgCgojIyMgJm5ic3A7Jm5ic3A7KGEpICAKCkNyZWF0ZSBhIHRyYWluaW5nIHNldCBjb250YWluaW5nIGEgcmFuZG9tIHNhbXBsZSBvZiA4MDAgb2JzZXJ2YXRpb25zLCBhbmQgYSB0ZXN0IHNldCBjb250YWluaW5nIHRoZSByZW1haW5pbmcgb2JzZXJ2YXRpb25zOgpgYGB7cn0KIyBQcmVsaW1zOgpzZXQuc2VlZCgxKQoKIyBEYXRhOgpkZiA8LSBPSgoKIyBUcmFpbi9UZXN0Ogp0cmFpbiA8LSBzYW1wbGUoMTpucm93KE9KKSwgODAwKQp0ZXN0IDwtIC10cmFpbgpgYGAKCiMjIyAmbmJzcDsmbmJzcDsoYikgIAoKRml0IGEgc3VwcG9ydCB2ZWN0b3IgY2xhc3NpZmllciB0byB0aGUgdHJhaW5pbmcgZGF0YSB1c2luZyBgY29zdCA9IDAuMDFgLCB3aXRoIGBQdXJjaGFzZWAgYXMgdGhlIHJlc3BvbnNlIGFuZCB0aGUgb3RoZXIgdmFyaWFibGVzIGFzIHByZWRpY3RvcnM6CmBgYHtyfQpzdmNfOCA8LSBzdm0oUHVyY2hhc2UgfiAuICwgZGF0YSA9IGRmW3RyYWluLCBdLCBrZXJuZWwgPSAibGluZWFyIiwgY29zdCA9IDAuMDEpCnN1bW1hcnkoc3ZjXzgpCmBgYAoKIyMjICZuYnNwOyZuYnNwOyhjKSAgCgpUcmFpbmluZyBlcnJvcjoKYGBge3J9CnN2Y184LnRyYWluLmVycm9yIDwtIG1lYW4ocHJlZGljdChzdmNfOCwgZGZbdHJhaW4sIF0pICE9IGRmJFB1cmNoYXNlW3RyYWluXSkKc3ZjXzgudHJhaW4uZXJyb3IKYGBgCgpUZXN0IGVycm9yOgpgYGB7cn0Kc3ZjXzgudGVzdC5lcnJvciA8LSBtZWFuKHByZWRpY3Qoc3ZjXzgsIGRmW3Rlc3QsIF0pICE9IGRmJFB1cmNoYXNlW3Rlc3RdKQpzdmNfOC50ZXN0LmVycm9yCmBgYAoKIyMjICZuYnNwOyZuYnNwOyhkKSAgCgpVc2UgdGhlIHR1bmUoKSBmdW5jdGlvbiB0byBzZWxlY3QgYW4gb3B0aW1hbCBgY29zdC5gIENvbnNpZGVyIHZhbHVlcyBpbiB0aGUgcmFuZ2UgMC4wMSB0byAxMC4KYGBge3J9CnNldC5zZWVkKDEpCmNvc3RzIDwtIGMgKDAuMDEsIDAuMDUsIDAuMSwgMC4yNSwgMC41LCAxLCAyLCA1LCAxMCkKc3ZjLm91dF84IDwtIHR1bmUoc3ZtLCBQdXJjaGFzZSB+IC4sIGRhdGEgPSBkZlt0cmFpbiwgXSwga2VybmVsID0gImxpbmVhciIsIHJhbmdlcyA9IGxpc3QoY29zdCA9IGNvc3RzKSkKc3ZjXzguY3YuZXJyb3IgPC0gc3ZjLm91dF84JHBlcmZvcm1hbmNlcyRlcnJvciAjIGV4dHJhY3QgdGhlIENWIGVycm9ycwpzdmNfOC5jdi5lcnJvcgpgYGAKClBsb3Q6CmBgYHtyfQpnZ3Bsb3QoZGF0YS5mcmFtZShjb3N0ID0gbG9nMTAoY29zdHMpLCBjdi5lcnJvciA9IHN2Y184LmN2LmVycm9yKSkgKwogIGdlb21fbGluZShhZXMoY29zdCwgY3YuZXJyb3IpLCBjb2xvciA9IElTTFJfb3JhbmdlKSArCiAgbGFicyh0aXRsZSA9ICJMaW5lYXIgS2VybmVsIC0gQ1YgRXJyb3IgUmF0ZSBhcyBGdW5jdGlvbiBvZiBDb3N0IiwKICAgICAgIHggPSBUZVgoIkxvZ197MTB9KENvc3QpIiksCiAgICAgICB5ID0gIkNWIEVycm9yIFJhdGUiKSArCiAgdGhlbWVfYncoKSArCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpCmBgYAoKIyMjICZuYnNwOyZuYnNwOyhlKSAgCgpUaGUgdHJhaW5pbmcgYW5kIHRlc3QgZXJyb3JzIGNhbiBiZSBvYnRhaW5lZCBieSB0cmFpbmluZyBTVkMgbW9kZWxzIHVzaW5nIGEgcmFuZ2Ugb2YgdmFsdWVzIGZvciBgY29zdGAgYW5kIHRoZW4gbWFraW5nIHByZWRpY3Rpb25zIG9uIHRoZSB0cmFpbmluZyBhbmQgdGVzdCBkYXRhIHJlc3BlY3RpdmVseToKYGBge3J9CnNldC5zZWVkKDEpCnN2Y184LnRyYWluLmVycm9yIDwtIHZlY3RvcigiZG91YmxlIiwgbGVuZ3RoKGNvc3RzKSkKc3ZjXzgudGVzdC5lcnJvciA8LSB2ZWN0b3IoImRvdWJsZSIsIGxlbmd0aChjb3N0cykpCmZvcihpIGluIDE6bGVuZ3RoKGNvc3RzKSkgewogIHN2YyA8LSBzdm0oUHVyY2hhc2UgfiAuLCBkYXRhID0gZGZbdHJhaW4sIF0sIGtlcm5lbCA9ICJsaW5lYXIiLCBjb3N0ID0gY29zdHNbaV0pCiAgCiAgIyBUcmFpbmluZyBFcnJvcjoKICBwcmVkcyA8LSBwcmVkaWN0KHN2YywgZGZbdHJhaW4sIF0pCiAgdHJhaW4uZXJyb3IgPC0gbWVhbihwcmVkcyAhPSBkZiRQdXJjaGFzZVt0cmFpbl0pCiAgc3ZjXzgudHJhaW4uZXJyb3JbaV0gPC0gdHJhaW4uZXJyb3IKICAKICAjIFRlc3QgRXJyb3I6CiAgcHJlZHMgPC0gcHJlZGljdChzdmMsIGRmW3Rlc3QsIF0pCiAgdGVzdC5lcnJvciA8LSBtZWFuKHByZWRzICE9IGRmJFB1cmNoYXNlW3Rlc3RdKQogIHN2Y184LnRlc3QuZXJyb3JbaV0gPC0gdGVzdC5lcnJvcgp9CgpzdmNfOC50cmFpbi5lcnJvcgpzdmNfOC50ZXN0LmVycm9yCmBgYAoKUGxvdCB0aGUgQ1YsIHRyYWluaW5nLCBhbmQgdGVzdCBlcnJvcnM6CmBgYHtyfQpsaWJyYXJ5KGxhdGV4MmV4cCkKc3ZjXzguZXJyb3JzIDwtIGRhdGEuZnJhbWUoY29zdCA9IGxvZzEwKGNvc3RzKSwKICAgICAgICAgICAgICAgICAgICAgICAgIGN2LmVycm9yID0gc3ZjXzguY3YuZXJyb3IsCiAgICAgICAgICAgICAgICAgICAgICAgICB0cmFpbi5lcnJvciA9IHN2Y184LnRyYWluLmVycm9yLAogICAgICAgICAgICAgICAgICAgICAgICAgdGVzdC5lcnJvciA9IHN2Y184LnRlc3QuZXJyb3IpCgojIHNlZSBodHRwczovL3N0YWNrb3ZlcmZsb3cuY29tL2EvNTA0OTY4OTkgYW5kIGh0dHBzOi8vc3RhY2tvdmVyZmxvdy5jb20vYS8xMDM1NTg0NCBmb3IgbWFraW5nIGxlZ2VuZApnMSA8LSBnZ3Bsb3Qoc3ZjXzguZXJyb3JzKSArCiAgZ2VvbV9saW5lKGFlcyhjb3N0LCBjdi5lcnJvciwgY29sb3IgPSAiQ1YiKSkgKwogIGdlb21fbGluZShhZXMoY29zdCwgdHJhaW4uZXJyb3IsIGNvbG9yID0gIlRyYWluIikpICsKICBnZW9tX2xpbmUoYWVzKGNvc3QsIHRlc3QuZXJyb3IsIGNvbG9yID0gIlRlc3QiKSkgKwogIHNjYWxlX2NvbG9yX21hbnVhbChuYW1lID0gIkVycm9yIFJhdGUiLCBicmVha3MgPSBjKCJUZXN0IiwgIlRyYWluIiwgIkNWIiksIHZhbHVlcyA9IGMoIlRlc3QiID0gIiMwMEJBMzgiLCAiQ1YiID0gIiNGODc2NkQiLCAiVHJhaW4iID0gIiM2MTlDRkYiKSkgKwogICNzY2FsZV9jb2xvcl9kaXNjcmV0ZShuYW1lID0gTlVMTCwgbGFiZWxzID0gYygiQ1YgRXJyb3IiLCAiVGVzdCBFcnJvciIsICJUcmFpbmluZyBFcnJvciIpKSArCiAgbGFicyh0aXRsZSA9ICJMaW5lYXIgS2VybmVsIC0gQ29tcGFyaXNvbiBvZiBDViwgVHJhaW5pbmcgYW5kIFRlc3QgRXJyb3IgUmF0ZXMiLAogICAgICAgeCA9IFRlWCgiTG9nX3sxMH0oQ29zdCkiKSwKICAgICAgIHkgPSAiRXJyb3IgUmF0ZSIpICsKICB0aGVtZV9idygpICsKICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSwKICAgICAgICBsZWdlbmQucG9zaXRpb24gPSBjKDAuOTcsIDAuOTUpLCBsZWdlbmQuanVzdGlmaWNhdGlvbiA9IGMoMSwgMSkpCmcxCmBgYAoKVGhlIHRyYWluaW5nIGVycm9yIHNlZW1zIHRvIGJlIGhpZ2hlciB0aGFuIHRoZSB0ZXN0IGVycm9yLgoKIyMjICZuYnNwOyZuYnNwOyhmKSAgCgojIyMjIFJhZGlhbCBLZXJuZWwgIAoKYGBge3J9CnNldC5zZWVkKDEpCnN2bV84X3JhZCA8LSBzdm0oUHVyY2hhc2UgfiAuICwgZGF0YSA9IGRmW3RyYWluLCBdLCBrZXJuZWwgPSAicmFkaWFsIiwgY29zdCA9IDAuMDEpCnN1bW1hcnkoc3ZtXzhfcmFkKQpgYGAKClRyYWluaW5nIGVycm9yOgpgYGB7cn0Kc3ZtXzhfcmFkLnRyYWluLmVycm9yIDwtIG1lYW4ocHJlZGljdChzdm1fOF9yYWQsIGRmW3RyYWluLCBdKSAhPSBkZiRQdXJjaGFzZVt0cmFpbl0pCnN2bV84X3JhZC50cmFpbi5lcnJvcgpgYGAKClRlc3QgZXJyb3I6CmBgYHtyfQpzdm1fOF9yYWQudGVzdC5lcnJvciA8LSBtZWFuKHByZWRpY3Qoc3ZtXzhfcmFkLCBkZlt0ZXN0LCBdKSAhPSBkZiRQdXJjaGFzZVt0ZXN0XSkKc3ZtXzhfcmFkLnRlc3QuZXJyb3IKYGBgCgpVc2UgQ1Y6CmBgYHtyfQpzZXQuc2VlZCgxKQpzdm0ub3V0XzhfcmFkIDwtIHR1bmUoc3ZtLCBQdXJjaGFzZSB+IC4sIGRhdGEgPSBkZlt0cmFpbiwgXSwga2VybmVsID0gInJhZGlhbCIsIHJhbmdlcyA9IGxpc3QoY29zdCA9IGNvc3RzKSkKc3ZtXzhfcmFkLmN2LmVycm9yIDwtIHN2bS5vdXRfOF9yYWQkcGVyZm9ybWFuY2VzJGVycm9yICMgZXh0cmFjdCB0aGUgQ1YgZXJyb3JzCnN2bV84X3JhZC5jdi5lcnJvcgpgYGAKClBsb3QgQ1YgZXJyb3I6CmBgYHtyfQpnZ3Bsb3QoZGF0YS5mcmFtZShjb3N0ID0gbG9nMTAoY29zdHMpLCBjdi5lcnJvciA9IHN2bV84X3JhZC5jdi5lcnJvcikpICsKICBnZW9tX2xpbmUoYWVzKGNvc3QsIGN2LmVycm9yKSwgY29sb3IgPSBJU0xSX29yYW5nZSkgKwogIGxhYnModGl0bGUgPSAiUmFkaWFsIEtlcm5lbCAtIENWIEVycm9yIFJhdGUgYXMgRnVuY3Rpb24gb2YgQ29zdCIsCiAgICAgICB4ID0gVGVYKCJMb2dfezEwfShDb3N0KSIpLAogICAgICAgeSA9ICJDViBFcnJvciBSYXRlIikgKwogIHRoZW1lX2J3KCkgKwogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQpgYGAKClRoZSB0cmFpbmluZyBhbmQgdGVzdCBlcnJvcnMgY2FuIGJlIG9idGFpbmVkIGJ5IHRyYWluaW5nIFNWTSBtb2RlbHMgdXNpbmcgYSByYW5nZSBvZiB2YWx1ZXMgZm9yIGBjb3N0YCBhbmQgdGhlbiBtYWtpbmcgcHJlZGljdGlvbnMgb24gdGhlIHRyYWluaW5nIGFuZCB0ZXN0IGRhdGEgcmVzcGVjdGl2ZWx5OgpgYGB7cn0Kc2V0LnNlZWQoMSkKc3ZtXzhfcmFkLnRyYWluLmVycm9yIDwtIHZlY3RvcigiZG91YmxlIiwgbGVuZ3RoKGNvc3RzKSkKc3ZtXzhfcmFkLnRlc3QuZXJyb3IgPC0gdmVjdG9yKCJkb3VibGUiLCBsZW5ndGgoY29zdHMpKQpmb3IoaSBpbiAxOmxlbmd0aChjb3N0cykpIHsKICBzdm1fOCA8LSBzdm0oUHVyY2hhc2UgfiAuLCBkYXRhID0gZGZbdHJhaW4sIF0sIGtlcm5lbCA9ICJyYWRpYWwiLCBjb3N0ID0gY29zdHNbaV0pCiAgCiAgIyBUcmFpbmluZyBFcnJvcjoKICBwcmVkcyA8LSBwcmVkaWN0KHN2bV84LCBkZlt0cmFpbiwgXSkKICB0cmFpbi5lcnJvciA8LSBtZWFuKHByZWRzICE9IGRmJFB1cmNoYXNlW3RyYWluXSkKICBzdm1fOF9yYWQudHJhaW4uZXJyb3JbaV0gPC0gdHJhaW4uZXJyb3IKICAKICAjIFRlc3QgRXJyb3I6CiAgcHJlZHMgPC0gcHJlZGljdChzdm1fOCwgZGZbdGVzdCwgXSkKICB0ZXN0LmVycm9yIDwtIG1lYW4ocHJlZHMgIT0gZGYkUHVyY2hhc2VbdGVzdF0pCiAgc3ZtXzhfcmFkLnRlc3QuZXJyb3JbaV0gPC0gdGVzdC5lcnJvcgp9Cgpzdm1fOF9yYWQudHJhaW4uZXJyb3IKc3ZtXzhfcmFkLnRlc3QuZXJyb3IKYGBgCgpQbG90IHRoZSBDViwgdHJhaW5pbmcsIGFuZCB0ZXN0IGVycm9yczoKYGBge3J9CmxpYnJhcnkobGF0ZXgyZXhwKQpzdm1fOF9yYWQuZXJyb3JzIDwtIGRhdGEuZnJhbWUoY29zdCA9IGxvZzEwKGNvc3RzKSwKICAgICAgICAgICAgICAgICAgICAgICAgIGN2LmVycm9yID0gc3ZtXzhfcmFkLmN2LmVycm9yLAogICAgICAgICAgICAgICAgICAgICAgICAgdHJhaW4uZXJyb3IgPSBzdm1fOF9yYWQudHJhaW4uZXJyb3IsCiAgICAgICAgICAgICAgICAgICAgICAgICB0ZXN0LmVycm9yID0gc3ZtXzhfcmFkLnRlc3QuZXJyb3IpCgojIHNlZSBodHRwczovL3N0YWNrb3ZlcmZsb3cuY29tL2EvNTA0OTY4OTkgYW5kIGh0dHBzOi8vc3RhY2tvdmVyZmxvdy5jb20vYS8xMDM1NTg0NCBmb3IgbWFraW5nIGxlZ2VuZApnMiA8LSBnZ3Bsb3Qoc3ZtXzhfcmFkLmVycm9ycykgKwogIGdlb21fbGluZShhZXMoY29zdCwgY3YuZXJyb3IsIGNvbG9yID0gIkNWIikpICsKICBnZW9tX2xpbmUoYWVzKGNvc3QsIHRyYWluLmVycm9yLCBjb2xvciA9ICJUcmFpbiIpKSArCiAgZ2VvbV9saW5lKGFlcyhjb3N0LCB0ZXN0LmVycm9yLCBjb2xvciA9ICJUZXN0IikpICsKICBzY2FsZV9jb2xvcl9tYW51YWwobmFtZSA9ICJFcnJvciBSYXRlIiwgYnJlYWtzID0gYygiVGVzdCIsICJUcmFpbiIsICJDViIpLCB2YWx1ZXMgPSBjKCJUZXN0IiA9ICIjMDBCQTM4IiwgIkNWIiA9ICIjRjg3NjZEIiwgIlRyYWluIiA9ICIjNjE5Q0ZGIikpICsKICAjc2NhbGVfY29sb3JfZGlzY3JldGUobmFtZSA9IE5VTEwsIGxhYmVscyA9IGMoIkNWIEVycm9yIiwgIlRlc3QgRXJyb3IiLCAiVHJhaW5pbmcgRXJyb3IiKSkgKwogIGxhYnModGl0bGUgPSAiUmFkaWFsIEtlcm5lbCAtIENvbXBhcmlzb24gb2YgQ1YsIFRyYWluaW5nIGFuZCBUZXN0IEVycm9yIFJhdGVzIiwKICAgICAgIHggPSBUZVgoIkxvZ197MTB9KENvc3QpIiksCiAgICAgICB5ID0gIkVycm9yIFJhdGUiKSArCiAgdGhlbWVfYncoKSArCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSksCiAgICAgICAgbGVnZW5kLnBvc2l0aW9uID0gYygwLjk3LCAwLjk1KSwgbGVnZW5kLmp1c3RpZmljYXRpb24gPSBjKDEsIDEpKQpnMgpgYGAKCldpdGggdGhlIHJhZGlhbCBrZXJuZWwsIHRoZSB0cmFpbmluZyBlcnJvciBpcyBsb3dlciB0aGFuIHRoZSB0ZXN0IGVycm9yLgoKIyMjICZuYnNwOyZuYnNwOyhnKSAgCgojIyMjIFBvbHlub21pYWwgS2VybmVsICAKCmBgYHtyfQpzZXQuc2VlZCgxKQpzdm1fOF9wb2x5IDwtIHN2bShQdXJjaGFzZSB+IC4gLCBkYXRhID0gZGZbdHJhaW4sIF0sIGtlcm5lbCA9ICJwb2x5bm9taWFsIiwgZGVncmVlID0gMiwgY29zdCA9IDAuMDEpCnN1bW1hcnkoc3ZtXzhfcG9seSkKYGBgCgpUcmFpbmluZyBlcnJvcjoKYGBge3J9CnN2bV84X3BvbHkudHJhaW4uZXJyb3IgPC0gbWVhbihwcmVkaWN0KHN2bV84X3BvbHksIGRmW3RyYWluLCBdKSAhPSBkZiRQdXJjaGFzZVt0cmFpbl0pCnN2bV84X3BvbHkudHJhaW4uZXJyb3IKYGBgCgpUZXN0IGVycm9yOgpgYGB7cn0Kc3ZtXzhfcG9seS50ZXN0LmVycm9yIDwtIG1lYW4ocHJlZGljdChzdm1fOF9wb2x5LCBkZlt0ZXN0LCBdKSAhPSBkZiRQdXJjaGFzZVt0ZXN0XSkKc3ZtXzhfcG9seS50ZXN0LmVycm9yCmBgYAoKVXNlIENWOgpgYGB7cn0Kc2V0LnNlZWQoMSkKc3ZtLm91dF84X3BvbHkgPC0gdHVuZShzdm0sIFB1cmNoYXNlIH4gLiwgZGF0YSA9IGRmW3RyYWluLCBdLCBrZXJuZWwgPSAicG9seW5vbWlhbCIsIGRlZ3JlZSA9IDIsIHJhbmdlcyA9IGxpc3QoY29zdCA9IGNvc3RzKSkKICAgICAgICAgICAgICNzdm0oUHVyY2hhc2UgfiAuICwgZGF0YSA9IGRmW3RyYWluLCBdLCBrZXJuZWwgPSAicG9seW5vbWlhbCIsIGRlZ3JlZSA9IDIsIGNvc3QgPSAwLjAxKQpzdm1fOF9wb2x5LmN2LmVycm9yIDwtIHN2bS5vdXRfOF9wb2x5JHBlcmZvcm1hbmNlcyRlcnJvciAjIGV4dHJhY3QgdGhlIENWIGVycm9ycwpzdm1fOF9wb2x5LmN2LmVycm9yCmBgYAoKUGxvdCBDViBlcnJvcjoKYGBge3J9CmdncGxvdChkYXRhLmZyYW1lKGNvc3QgPSBsb2cxMChjb3N0cyksIGN2LmVycm9yID0gc3ZtXzhfcG9seS5jdi5lcnJvcikpICsKICBnZW9tX2xpbmUoYWVzKGNvc3QsIGN2LmVycm9yKSwgY29sb3IgPSBJU0xSX29yYW5nZSkgKwogIGxhYnModGl0bGUgPSAiUG9seW5vbWlhbCBLZXJuZWwgKGQgPSAyKSAtIENWIEVycm9yIFJhdGUgYXMgRnVuY3Rpb24gb2YgQ29zdCIsCiAgICAgICB4ID0gVGVYKCJMb2dfezEwfShDb3N0KSIpLAogICAgICAgeSA9ICJDViBFcnJvciBSYXRlIikgKwogIHRoZW1lX2J3KCkgKwogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQpgYGAKClRoZSB0cmFpbmluZyBhbmQgdGVzdCBlcnJvcnMgY2FuIGJlIG9idGFpbmVkIGJ5IHRyYWluaW5nIFNWQyBtb2RlbHMgdXNpbmcgYSByYW5nZSBvZiB2YWx1ZXMgZm9yIGBjb3N0YCBhbmQgdGhlbiBtYWtpbmcgcHJlZGljdGlvbnMgb24gdGhlIHRyYWluaW5nIGFuZCB0ZXN0IGRhdGEgcmVzcGVjdGl2ZWx5OgpgYGB7cn0Kc2V0LnNlZWQoMSkKc3ZtXzhfcG9seS50cmFpbi5lcnJvciA8LSB2ZWN0b3IoImRvdWJsZSIsIGxlbmd0aChjb3N0cykpCnN2bV84X3BvbHkudGVzdC5lcnJvciA8LSB2ZWN0b3IoImRvdWJsZSIsIGxlbmd0aChjb3N0cykpCmZvcihpIGluIDE6bGVuZ3RoKGNvc3RzKSkgewogIHN2bV84IDwtIHN2bShQdXJjaGFzZSB+IC4sIGRhdGEgPSBkZlt0cmFpbiwgXSwga2VybmVsID0gInBvbHlub21pYWwiLCBkZWdyZWUgPSAyLCBjb3N0ID0gY29zdHNbaV0pCiAgCiAgIyBUcmFpbmluZyBFcnJvcjoKICBwcmVkcyA8LSBwcmVkaWN0KHN2bV84LCBkZlt0cmFpbiwgXSkKICB0cmFpbi5lcnJvciA8LSBtZWFuKHByZWRzICE9IGRmJFB1cmNoYXNlW3RyYWluXSkKICBzdm1fOF9wb2x5LnRyYWluLmVycm9yW2ldIDwtIHRyYWluLmVycm9yCiAgCiAgIyBUZXN0IEVycm9yOgogIHByZWRzIDwtIHByZWRpY3Qoc3ZtXzgsIGRmW3Rlc3QsIF0pCiAgdGVzdC5lcnJvciA8LSBtZWFuKHByZWRzICE9IGRmJFB1cmNoYXNlW3Rlc3RdKQogIHN2bV84X3BvbHkudGVzdC5lcnJvcltpXSA8LSB0ZXN0LmVycm9yCn0KCnN2bV84X3BvbHkudHJhaW4uZXJyb3IKc3ZtXzhfcG9seS50ZXN0LmVycm9yCmBgYAoKUGxvdCB0aGUgQ1YsIHRyYWluaW5nLCBhbmQgdGVzdCBlcnJvcnM6CmBgYHtyfQpsaWJyYXJ5KGxhdGV4MmV4cCkKc3ZtXzhfcG9seS5lcnJvcnMgPC0gZGF0YS5mcmFtZShjb3N0ID0gbG9nMTAoY29zdHMpLAogICAgICAgICAgICAgICAgICAgICAgICAgY3YuZXJyb3IgPSBzdm1fOF9wb2x5LmN2LmVycm9yLAogICAgICAgICAgICAgICAgICAgICAgICAgdHJhaW4uZXJyb3IgPSBzdm1fOF9wb2x5LnRyYWluLmVycm9yLAogICAgICAgICAgICAgICAgICAgICAgICAgdGVzdC5lcnJvciA9IHN2bV84X3BvbHkudGVzdC5lcnJvcikKCiMgc2VlIGh0dHBzOi8vc3RhY2tvdmVyZmxvdy5jb20vYS81MDQ5Njg5OSBhbmQgaHR0cHM6Ly9zdGFja292ZXJmbG93LmNvbS9hLzEwMzU1ODQ0IGZvciBtYWtpbmcgbGVnZW5kCmczIDwtIGdncGxvdChzdm1fOF9wb2x5LmVycm9ycykgKwogIGdlb21fbGluZShhZXMoY29zdCwgY3YuZXJyb3IsIGNvbG9yID0gIkNWIikpICsKICBnZW9tX2xpbmUoYWVzKGNvc3QsIHRyYWluLmVycm9yLCBjb2xvciA9ICJUcmFpbiIpKSArCiAgZ2VvbV9saW5lKGFlcyhjb3N0LCB0ZXN0LmVycm9yLCBjb2xvciA9ICJUZXN0IikpICsKICBzY2FsZV9jb2xvcl9tYW51YWwobmFtZSA9ICJFcnJvciBSYXRlIiwgYnJlYWtzID0gYygiVGVzdCIsICJUcmFpbiIsICJDViIpLCB2YWx1ZXMgPSBjKCJUZXN0IiA9ICIjMDBCQTM4IiwgIkNWIiA9ICIjRjg3NjZEIiwgIlRyYWluIiA9ICIjNjE5Q0ZGIikpICsKICAjc2NhbGVfY29sb3JfZGlzY3JldGUobmFtZSA9IE5VTEwsIGxhYmVscyA9IGMoIkNWIEVycm9yIiwgIlRlc3QgRXJyb3IiLCAiVHJhaW5pbmcgRXJyb3IiKSkgKwogIGxhYnModGl0bGUgPSAiUG9seW5vbWlhbCBLZXJuZWwgKGQgPSAyKSAtIENvbXBhcmlzb24gb2YgQ1YsIFRyYWluaW5nIGFuZCBUZXN0IEVycm9yIFJhdGVzIiwKICAgICAgIHggPSBUZVgoIkxvZ197MTB9KENvc3QpIiksCiAgICAgICB5ID0gIkVycm9yIFJhdGUiKSArCiAgdGhlbWVfYncoKSArCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSksCiAgICAgICAgbGVnZW5kLnBvc2l0aW9uID0gYygwLjk3LCAwLjk1KSwgbGVnZW5kLmp1c3RpZmljYXRpb24gPSBjKDEsIDEpKQpnMwpgYGAKCldpdGggdGhlIHJhZGlhbCBrZXJuZWwsIHRoZSB0cmFpbmluZyBlcnJvciBpcyBsb3dlciB0aGFuIHRoZSB0ZXN0IGVycm9yLgoKIyMjICZuYnNwOyZuYnNwOyhoKSAgCgpDb21wYXJpc29uIG9mIHRocmVlIGtlcm5lbHM6CmBgYHtyIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD00LjV9CnBsb3RfZ3JpZChwbG90bGlzdCA9IGxpc3QoZzEgKyBnZ3RpdGxlKCJMaW5lYXIiKSArIHNjYWxlX3lfY29udGludW91cyhsaW1pdHMgPSBjKDAuMTQsIDAuNCksIGJyZWFrcyA9IHNlcSgwLjEsIDAuNCwgYnkgPSAwLjA1KSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgZzIgKyBnZ3RpdGxlKCJSYWRpYWwiKSArIHNjYWxlX3lfY29udGludW91cyhsaW1pdHMgPSBjKDAuMTQsIDAuNCksIGJyZWFrcyA9IHNlcSgwLjEsIDAuNCwgYnkgPSAwLjA1KSkgKyB0aGVtZShheGlzLnRpdGxlLnkgPSBlbGVtZW50X2JsYW5rKCkpLAogICAgICAgICAgICAgICAgICAgICAgICAgIGczICsgZ2d0aXRsZSgiUG9seW5vbWlhbCIpICsgc2NhbGVfeV9jb250aW51b3VzKGxpbWl0cyA9IGMoMC4xNCwgMC40KSwgYnJlYWtzID0gc2VxKDAuMSwgMC40LCBieSA9IDAuMDUpKSArIHRoZW1lKGF4aXMudGl0bGUueSA9IGVsZW1lbnRfYmxhbmsoKSkpLCBucm93ID0gMSkKYGBg